LeetCode Reorder List 鏈表重排序 (中點分割 + 反轉 + 合併)

問題

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

三步走策略

1. 找中點：快慢指針，慢指針走到中點 (偶數節點取前中點)。
2. 反轉後半部分鏈表：從中點後一個節點開始反轉。
3. 合併兩條鏈表：交替取前半、後半節點串聯。

代碼 (C++)

class Solution {
public:
    ListNode* findMid(ListNode* head) {
        ListNode *slow = head, *fast = head;
        while (fast && fast->next) { fast = fast->next->next; slow = slow->next; }
        return slow;
    }
    ListNode* reverse(ListNode* head) {
        ListNode *prev = nullptr, *curr = head;
        while (curr) { ListNode* nxt = curr->next; curr->next = prev; prev = curr; curr = nxt; }
        return prev;
    }
    void reorderList(ListNode* head) {
        if (!head) return;
        ListNode* mid = findMid(head);
        ListNode* second = reverse(mid->next);
        mid->next = nullptr;
        ListNode* first = head;
        while (second) {
            ListNode* fnext = first->next;
            ListNode* snext = second->next;
            first->next = second;
            second->next = fnext;
            first = fnext;
            second = snext;
        }
    }
};

關鍵點

• 中點定義：`findMid` 返回前中點，斷開 `mid->next` 避免環。
• 合併時 `second` 可能比 `first` 短 (奇數長度)，循環條件 `while (second)` 正確處理。
• 時間 O(n)，空間 O(1)。