題目意思： 翻轉(zhuǎn)給定區(qū)間[m,n]的鏈表。 第一個節(jié)點(diǎn)m=1。 1<=m<=n<=length。
解題思路： 就我目前學(xué)習(xí)到的，有用指向指針的指針的，有插入，有逆轉(zhuǎn)的。但是所有方法的核心，都其實(shí)是一個算法，就是利用3個指針修改區(qū)間內(nèi)的節(jié)點(diǎn)的next值，且要保證已修改的鏈表是可以被找到的，即可以連入原鏈表中。 假設(shè)有一個鏈表有1,2,3,4,5,6，6個節(jié)點(diǎn)。m=2，n=5。 我們添加一個dummy節(jié)點(diǎn)，方便操作第一個節(jié)點(diǎn)。
首先讓pre指向第m個節(jié)點(diǎn)前面那個，cur指向第m個節(jié)點(diǎn)，p1指向m的下一個節(jié)點(diǎn)，因?yàn)閜1有可能是NULL，所以當(dāng)p1不是NULL的時候，p2指向p1的下一個節(jié)點(diǎn)。 上圖畫出了這幾個指針指向情況的開始狀態(tài)和我們希望的終止?fàn)顟B(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 };
分類: Leetcode 解題 |
|
|
來自： 雪柳花明 > 《LeetCode》
