## Monday, December 31, 2012

### [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 m, n satisfy the following condition:
1 ≤ m  n ≤ length of list.
» Solve this problem

[解题思路]

1. 找到m节点的前一个指针pre（加个safe guard可避免头指针的问题）
2. 从m节点开始往后reverse N个节点（双指针，cur，post）
3. 合并pre链表，cur链表及post链表。

{1,2,3}, 3,3
{1,2,3}, 1,1
{1,2,3}, 1,3

``````1:       ListNode *reverseBetween(ListNode *head, int m, int n) {
2:            // Start typing your C/C++ solution below
3:            // DO NOT write int main() function
4:            int step = n-m;
5:            ListNode* safeG = new ListNode(-1); //intro a safe guard to avoid handle head case
9:            while(m>1)
10:            {
11:                 pre=pre->next;
12:                 m--;
13:            }
14:            ListNode* cur = pre->next, *post = cur->next;
15:            if(step>=1)
16:            {
17:                 while(step>0 && post!=NULL)
18:                 {
19:                      ListNode* temp = post->next;
20:                      post->next = cur;
21:                      cur = post;
22:                      post = temp;
23:                      step--;
24:                 }
25:                 ListNode* temp = pre->next;
26:                 pre->next = cur;
27:                 temp->next = post;
28:            }