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 reverseList45             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 n51 52             p->next = post_n; //connect m and post_n53             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 };