LeetCode Reorder List：鏈表重排序原地算法

LeetCode Reorder List：鏈表原地重排序

給定單鏈表 L0→L1→…→Ln-1→Ln，重排為 L0→Ln→L1→Ln-1→L2→Ln-2→…。要求原地操作，不修改節點值。

方法一：陣列輔助（易理解）

遍歷鏈表將節點指針存入 vector，雙指針頭尾向中間重建鏈表。時間 O(n)，空間 O(n)。

void reorderList(ListNode *head) {
    vector arr;
    for (ListNode* p = head; p; p = p->next) arr.push_back(p);
    if (arr.size() < 3) return;
    int i = 1, len = arr.size() - 1, tag = 0;
    ListNode* p = head;
    while (tag < len/2) {
        p->next = arr[len--]; p = p->next;
        p->next = arr[i++]; p = p->next;
        tag++;
    }
    p->next = NULL;
}

方法二：找中點 + 反轉後半部 + 合併（O(1) 空間）

1. 快慢指針找中點。
2. 將後半部原地反轉（頭插法）。
3. 交替合併前半部和反轉後的後半部。
時間 O(n)，空間 O(1)。

void reorderList(ListNode *head) {
    if (!head || !head->next) return;
    ListNode *p = head, *q = head;
    while (q->next && q->next->next) { p = p->next; q = q->next->next; }
    q = p->next;
    while (q->next) {
        ListNode* tmp = p->next;
        p->next = q->next;
        q->next = q->next->next;
        p->next->next = tmp;
    }
    q = head;
    while (p != q && p->next) {
        ListNode* tmp = q->next;
        q->next = p->next;
        p->next = p->next->next;
        q->next->next = tmp;
        q = q->next->next;
    }
}

方法二展示了鏈表操作的核心技巧：中點分割、原地反轉、交替合併，是面試高頻考點。