[LeetCode] 143.Reorder List 鏈表重排序

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You may not modify the values in the list's nodes, only nodes itself may be changed.

Example 1:

Given 1->2->3->4, reorder it to 1->4->2->3.

Example 2:

Given 1->2->3->4->5, reorder it to 1->5->2->4->3.

這道鏈表重排序問(wèn)題可以拆分為以下三個(gè)小問(wèn)題：

1. 使用快慢指針來(lái)找到鏈表的中點(diǎn)，并將鏈表從中點(diǎn)處斷開(kāi)，形成兩個(gè)獨(dú)立的鏈表。

2. 將第二個(gè)鏈翻轉(zhuǎn)。

3. 將第二個(gè)鏈表的元素間隔地插入第一個(gè)鏈表中。

解法一：

class Solution {
public:
    void reorderList(ListNode *head) {
        if (!head || !head->next || !head->next->next) return;
        ListNode *fast = head, *slow = head;
        while (fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode *mid = slow->next;
        slow->next = NULL;
        ListNode *last = mid, *pre = NULL;
        while (last) {
            ListNode *next = last->next;
            last->next = pre;
            pre = last;
            last = next;
        }
        while (head && pre) {
            ListNode *next = head->next;
            head->next = pre;
            pre = pre->next;
            head->next->next = next;
            head = next;
        }
    }
};

我們嘗試著看能否寫(xiě)法上簡(jiǎn)潔一些，上面的第二步是將后半段鏈表翻轉(zhuǎn)，那么我們其實(shí)可以借助棧的后進(jìn)先出的特性來(lái)做，如果我們按順序?qū)⑺械慕Y(jié)點(diǎn)壓入棧，那么出棧的時(shí)候就可以倒序了，實(shí)際上就相當(dāng)于翻轉(zhuǎn)了鏈表。由于只需將后半段鏈表翻轉(zhuǎn)，那么我們就要控制出棧結(jié)點(diǎn)的個(gè)數(shù)，還好棧可以直接得到結(jié)點(diǎn)的個(gè)數(shù)，我們減1除以2，就是要出棧結(jié)點(diǎn)的個(gè)數(shù)了。然后我們要做的就是將每次出棧的結(jié)點(diǎn)隔一個(gè)插入到正確的位置，從而滿(mǎn)足題目中要求的順序，鏈表插入結(jié)點(diǎn)的操作就比較常見(jiàn)了，這里就不多解釋了，最后記得斷開(kāi)棧頂元素后面的結(jié)點(diǎn)，比如對(duì)于 1->2->3->4，棧頂只需出一個(gè)結(jié)點(diǎn)4，然后加入原鏈表之后為 1->4->2->3->(4)，因?yàn)樵谠湵碇薪Y(jié)點(diǎn)3之后是連著結(jié)點(diǎn)4的，雖然我們將結(jié)點(diǎn)4取出插入到結(jié)點(diǎn)1和2之間，但是結(jié)點(diǎn)3后面的指針還是連著結(jié)點(diǎn)4的，所以我們要斷開(kāi)這個(gè)連接，這樣才不會(huì)出現(xiàn)環(huán)，由于此時(shí)結(jié)點(diǎn)3在棧頂，所以我們直接斷開(kāi)棧頂結(jié)點(diǎn)即可，參見(jiàn)代碼如下：

解法二：

class Solution {
public:
    void reorderList(ListNode *head) {
        if (!head || !head->next || !head->next->next) return;
        stack<ListNode*> st;
        ListNode *cur = head;
        while (cur) {
            st.push(cur);
            cur = cur->next;
        }
        int cnt = ((int)st.size() - 1) / 2;
        cur = head;
        while (cnt-- > 0) {
            auto t = st.top(); st.pop();
            ListNode *next = cur->next;
            cur->next = t;
            t->next = next;
            cur = next;
        }
        st.top()->next = NULL;
    }
};

參考資料：

https://leetcode.com/problems/reorder-list/

https://leetcode.com/problems/reorder-list/discuss/45175/Java-solution-with-stack

https://leetcode.com/problems/reorder-list/discuss/44992/Java-solution-with-3-steps

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

最新評(píng)論