題目 143：「重排鏈結串列 (Reorder List)」要求我們對單向鏈結串列進行重新排列，使得節點順序變為 L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …。這題考驗我們對鏈結串列的操作能力，特別是對鏈結串列結構的理解和操作技巧。

題目：

給定一個單向鏈結串列 head，將其重新排列，使得每個節點的順序按照以下方式變化：

• 將原始鏈結串列的前半部分和後半部分交錯進行拼接。

例如，對於鏈結串列 [1,2,3,4]，重排後結果為 [1,4,2,3]。對於鏈結串列 [1,2,3,4,5]，重排後結果為 [1,5,2,4,3]。

範例：

1. 輸入：head = [1,2,3,4]

   • 輸出：[1,4,2,3]

2. 輸入：head = [1,2,3,4,5]

   • 輸出：[1,5,2,4,3]

解題思路

問題拆分成將 list 切成兩半，再將後半段反轉，接著再將兩個 list 交替合併起來，

切成兩半可以先找到中點就可以分成兩半 （876 這題用雙指標法解過了），接著反轉 list (206 這題解過了)，將兩個 list 合併起來 (跟 0021 這題類似)

這題聚集了多個 leetcode 問題，這題結合了前面的知識技巧，

實作：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast->next != nullptr && fast->next->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }

        ListNode* second = reverse(slow->next);
        slow->next = nullptr;

        ListNode* first = head;
        while (second != nullptr) {
            ListNode* fnext = first->next;
            ListNode* snext = second->next;
            first->next = second;
            second->next = fnext;

            first = fnext;
            second = snext;
        }
    }
private:
    ListNode* reverse(ListNode* head) {
        ListNode* curr = head;
        ListNode* prev = nullptr;
        while (curr != nullptr) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        // curr is nullptr, prev is the head
        return prev;
    }
};

參考：
#143. Reorder List