## Thursday, November 20, 2014

### [LeetCode] Reverse Linked List II

Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given `1->2->3->4->5->NULL`m = 2 and n = 4,
return `1->4->3->2->5->NULL`.
Note:
Given mn satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

1. 找到原链表中第m-1个节点start：反转后的部分将接回改节点后。

D->1->2->3->4->5->NULL
|
st

2. 将从p = start->next开始，长度为L = n-m+1的部分链表反转。
__________
|                  |
|                 V
D->1->2<-3<-4    5->NULL
|     |           |
st    p          h0

3. 最后接回

__________
|                  |
|                 V
D->1   2<-3<-4    5->NULL
|________|

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28``` ```class Solution { public: ListNode *reverseBetween(ListNode *head, int m, int n) { if(m<1 || m>=n || !head) return head; ListNode *dummy = new ListNode(0); dummy->next = head; head = dummy; // move head to (m-1)th node for(int i=0; inext; // reverse list from pre with length n-m+1 ListNode *pre = head->next, *cur = pre->next; for(int i=0; inext; cur->next = pre; pre = cur; cur = temp; } head->next->next = cur; head->next = pre; head = dummy->next; delete dummy; return head; } }; ```