[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.

方法一：我先写了个简单的reverseList，然后基于reverseList，要找到pre_m, post_n, 然后断开连接，重新连接即可。

吐槽一下LeetCode，竟然是基于打印检测结果，我的程序中有些打印语句，死活过不了，看来半天，没找出问题，去掉打印语句后，就没问题了。。

上code，唯一注意的一点是link是从1 开始的，所以 pre_m 是第m-1个，跳出while循环时，p指向的是第n个，post_n就是p->next.

另外，为了方便出来m=1的情况，加了个dummy的空Node，省去了一大堆判断，是个好方法。。

 1 ListNode * reverseList(ListNode* head)
 2 {
 3     if(head == NULL) return NULL;
 4 
 5     ListNode *pre = NULL;
 6     ListNode *cur = head;
 7     ListNode *next = NULL;
 8 
 9     while(cur)
10     {
11         next = cur->next;
12         cur->next = pre;
13 
14         pre = cur;
15         cur = next;
16     }
17 
18     return pre;
19 
20 }
21 class Solution {
22     public:
23         ListNode *reverseBetween(ListNode *head, int m, int n)
24         {
25             ListNode dummy(100);
26             dummy.next = head;
27 
28             ListNode *pre_m = &dummy;
29             ListNode *post_n = NULL;
30             ListNode *p = head;
31             int cnt = 1;
32 
33             while(cnt  < n)
34             {
35                 if(cnt == (m-1))
36                     pre_m = p;
37                 if(p)
38                     p = p->next;
39                 cnt++;
40             }
41 
42             post_n = p->next;
43 
44             // build a signle link, and call reverseList
45             p->next = NULL;
46 
47             //store m node in variable p;
48             p = pre_m->next;
49 
50             pre_m->next = reverseList(pre_m->next);  // connect pre_m and n
51 
52             p->next = post_n; //connect m and post_n
53             return dummy.next;
54 
55         }
56 
57 };

方法二：不用reverseList，直接原地reverse，注意处理好pre_m 的找法。。

 1 class Solution {
 2     public:
 3       ListNode *reverseBetween(ListNode *head, int m, int n)
 4         {
 5             ListNode dummy(-1);
 6             dummy.next = head;
 7 
 8             ListNode *pre_m = &dummy;
 9             ListNode *p = head;
10             int cnt = 1;
11 
12             for(; cnt < m; cnt ++)
13             {
14                 if(cnt == (m-1))
15                     pre_m = p;
16                 p = p->next;
17             }
18             //now p point to m 
19 
20             ListNode *pre = NULL;
21             ListNode *cur = p;
22             ListNode *next = NULL;
23             for( cnt = m ; cnt <= n; cnt ++)
24             {
25 
26                next = cur->next;
27                cur->next = pre;
28 
29                pre = cur;
30                cur = next;
31             }
32             // now pre points to n;
33             // now cur points to post_n;
34 
35             pre_m ->next = pre;
36             p->next = cur;
37 
38             return dummy.next;
39         }
40 
41 };

方法三：方法二中寻找pre_m的方法略微麻烦，有更好的方法，dummy节点的index是0，所以，可以利用这一点去寻找pre_m，下面的代码中p完全可以不要，不过为了清楚，

 1 class Solution {
 2     public:
 3       ListNode *reverseBetween(ListNode *head, int m, int n)
 4         {
 5             ListNode dummy(-1);
 6             dummy.next = head;
 7 
 8             ListNode *pre_m = &dummy;
 9             ListNode *p = head;
10             int cnt = 0;
11 
12             for(; cnt < m-1; cnt ++)
13             {
14                 pre_m = pre_m->next;
15             }
16             //now pre_m point to m-1;
17             p = pre_m->next;
18             //now p point to m 
19 
20 
21             ListNode *pre = NULL;
22             ListNode *cur = p;
23             ListNode *next = NULL;
24             for( cnt = m ; cnt <= n; cnt ++)
25             {
26 
27                next = cur->next;
28                cur->next = pre;
29 
30                pre = cur;
31                cur = next;
32             }
33             // now pre points to n;
34             // now cur points to post_n;
35 
36             pre_m ->next = pre;
37             p->next = cur;
38 
39             return dummy.next;
40         }
41 
42 };