Reverse Linked List II
Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given1->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.
題目意思：
翻轉給定區(qū)間[m,n]的鏈表。
第一個節(jié)點m=1。
1<=m<=n<=length。
解題思路：
就我目前學習到的，有用指向指針的指針的，有插入，有逆轉的。但是所有方法的核心，都其實是一個算法，就是利用3個指針修改區(qū)間內(nèi)的節(jié)點的next值，且要保證已修改的鏈表是可以被找到的，即可以連入原鏈表中。
假設有一個鏈表有1,2,3,4,5,6，6個節(jié)點。m=2，n=5。
我們添加一個dummy節(jié)點，方便操作第一個節(jié)點。
首先讓pre指向第m個節(jié)點前面那個，cur指向第m個節(jié)點，p1指向m的下一個節(jié)點，因為p1有可能是NULL，所以當p1不是NULL的時候，p2指向p1的下一個節(jié)點。
上圖畫出了這幾個指針指向情況的開始狀態(tài)和我們希望的終止狀態(tài)。
在最終狀態(tài)下，再通過其中方框中的兩步就可以我們需要的鏈表了。
而cur，p1，p2三個指針在區(qū)間內(nèi)向前移動并且將p1的next指向cur的過程則包含在一個for循環(huán)內(nèi)部。如下：
代碼如下：
1 class Solution { 2 public: 3 ListNode *reverseBetween(ListNode *head, int m, int n) { 4 ListNode *dummy = new ListNode(0); 5 dummy->next = head; 6 7 ListNode *pre = dummy, *cur = head; 8 for(int i = 1; i < m; i++){ 9 pre = cur;10 cur = cur->next;11 }12 13 ListNode *p1,*p2;14 if(cur)15 p1 = cur->next;16 if(p1)17 p2 = p1->next;18 for(int j = m; j < n; j++){19 p1->next = cur;20 cur = p1;21 p1 = p2;22 if(p2) p2 = p2->next;23 }24 pre->next->next = p1;25 pre->next = cur;26 27 return dummy->next;28 }29 };
