[LeetCode] 92. Reverse Linked List II 倒置鏈表之二

Reverse a linked list from position m to n. Do it in one-pass.

Note: 1 ≤ m ≤ n ≤ length of list.

Example:

Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL

很奇怪為何沒有倒置鏈表之一，就來了這個倒置鏈表之二，不過猜也能猜得到之一就是單純的倒置整個鏈表，而這道作為延伸的地方就是倒置其中的某一小段。對于鏈表的問題，根據(jù)以往的經(jīng)驗(yàn)一般都是要建一個dummy node，連上原鏈表的頭結(jié)點(diǎn)，這樣的話就算頭結(jié)點(diǎn)變動了，我們還可以通過dummy->next來獲得新鏈表的頭結(jié)點(diǎn)。這道題的要求是只通過一次遍歷完成，就拿題目中的例子來說，變換的是2,3,4這三個點(diǎn)，我們需要找到第一個開始變換結(jié)點(diǎn)的前一個結(jié)點(diǎn)，只要讓pre向后走m-1步即可，為啥要減1呢，因?yàn)轭}目中是從1開始計(jì)數(shù)的，這里只走了1步，就是結(jié)點(diǎn)1，用pre指向它。萬一是結(jié)點(diǎn)1開始變換的怎么辦，這就是我們?yōu)樯兑胐ummy結(jié)點(diǎn)了，pre也可以指向dummy結(jié)點(diǎn)。然后就要開始交換了，由于一次只能交換兩個結(jié)點(diǎn)，所以我們按如下的交換順序：

1 -> 2 -> 3 -> 4 -> 5 -> NULL

1 -> 3 -> 2 -> 4 -> 5 -> NULL

1 -> 4 -> 3 -> 2 -> 5 -> NULL

我們可以看出來，總共需要n-m步即可，第一步是將結(jié)點(diǎn)3放到結(jié)點(diǎn)1的后面，第二步將結(jié)點(diǎn)4放到結(jié)點(diǎn)1的后面。這是很有規(guī)律的操作，那么我們就說一個就行了，比如剛開始，pre指向結(jié)點(diǎn)1，cur指向結(jié)點(diǎn)2，然后我們建立一個臨時(shí)的結(jié)點(diǎn)t，指向結(jié)點(diǎn)3（注意我們用臨時(shí)變量保存某個結(jié)點(diǎn)就是為了首先斷開該結(jié)點(diǎn)和前面結(jié)點(diǎn)之間的聯(lián)系，這可以當(dāng)作一個規(guī)律記下來），然后我們斷開結(jié)點(diǎn)2和結(jié)點(diǎn)3，將結(jié)點(diǎn)2的next連到結(jié)點(diǎn)4上，也就是 cur->next = t->next，再把結(jié)點(diǎn)3連到結(jié)點(diǎn)1的后面結(jié)點(diǎn)（即結(jié)點(diǎn)2）的前面，即 t->next = pre->next，最后再將原來的結(jié)點(diǎn)1和結(jié)點(diǎn)2的連接斷開，將結(jié)點(diǎn)1連到結(jié)點(diǎn)3，即 pre->next = t。這樣我們就完成了將結(jié)點(diǎn)3取出，加入結(jié)點(diǎn)1的后方。第二步將結(jié)點(diǎn)4取出，加入結(jié)點(diǎn)1的后方，也是同樣的操作，這里就不多說了，請大家自己嘗試下吧，參見代碼如下：

class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        ListNode *dummy = new ListNode(-1), *pre = dummy;
        dummy->next = head;
        for (int i = 0; i < m - 1; ++i) pre = pre->next;
        ListNode *cur = pre->next;
        for (int i = m; i < n; ++i) {
            ListNode *t = cur->next;
            cur->next = t->next;
            t->next = pre->next;
            pre->next = t;
        }
        return dummy->next;
    }
};

到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(倒置鏈表之二)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)倒置鏈表之二內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論