題目： LeetCode - 143. Reorder List

題目說明

給一個 List，依照題目的要求重新排序。
※ 題目規定不能改變 node 的值。

解題思路

我們先取得中間的節點 ( 方法可以參考本篇文章：LeetCode - 876 解題紀錄 )，接著將中間到尾端的節點反轉，最後依照要求重新連接即可。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    void reorderList(ListNode* head) {
        if(!head) return;
        auto mid = findMid(head), l1 = head, l2 = mid->next;
        mid->next = nullptr;
        l2 = _reverse(l2);
        while(l1 && l2)
        {
            auto _next = l1->next;
            l1->next = l2;
            l2 = l2->next;
            l1->next->next = _next;
            l1 = _next;
        }
    }
private:
    ListNode* findMid(ListNode* head)
    {
        auto slow = head, fast = head;
        while(fast && fast->next) fast = fast->next->next, slow = slow->next;
        return slow;
    }
    
    ListNode* _reverse(ListNode* head)
    {
        ListNode* newhead = nullptr;
        while(head)
        {
            auto _next = head->next;
            head->next = newhead;
            newhead = head;
            head = _next;
        }
        return newhead;
    }
};