LeetCode Reorder List：單鏈表就地重排序 O(1) 空間解法

題目要求

給定單鏈表 L₀→L₁→…→Lₙ₋₁→Lₙ，重排為 L₀→Lₙ→L₁→Lₙ₋₁→L₂→Lₙ₋₂→…。要求在原鏈表上操作，不修改節點值，空間複雜度 O(1)。

解題步驟

1. 找中點：快慢指針或計算長度後遍歷到中點，將鏈表分為前後兩半。
2. 反轉後半部分鏈表：從中點下一個節點開始，就地反轉鏈表。
3. 合併兩條鏈表：交替取前半部分與反轉後的後半部分節點重新鏈接。

代碼實現（Java）

public void reorderList(ListNode head) {
    if (head == null || head.next == null || head.next.next == null) return;

    // 1. 計算長度並找到中點
    int len = 0;
    ListNode cur = head;
    while (cur != null) { len++; cur = cur.next; }
    int half = (len + 1) / 2;

    cur = head;
    ListNode second = head.next;
    for (int i = 1; i < half; i++) {
        cur = second;
        second = second.next;
    }
    cur.next = null; // 斷開前半部分

    // 2. 反轉後半部分鏈表
    ListNode secondHead = second;
    cur = second.next;
    secondHead.next = null;
    while (cur != null) {
        ListNode temp = cur;
        cur = cur.next;
        temp.next = secondHead;
        secondHead = temp;
    }

    // 3. 交替合併
    ListNode cur1 = head, cur2 = secondHead;
    while (cur2 != null) {
        ListNode next1 = cur1.next;
        ListNode next2 = cur2.next;
        cur2.next = cur1.next;
        cur1.next = cur2;
        cur1 = next1;
        cur2 = next2;
    }
}

關鍵點解析

• 中點計算：(len + 1) / 2 保證奇數長度時前半部分多一個節點。
• 就地反轉：使用三指針（secondHead, cur, temp）無需額外空間。
• 合併邏輯：先保存 next1, next2，再重新鏈接，避免斷鏈。

複雜度分析

• 時間：O(N) —— 三次線性遍歷（找中點、反轉、合併）。
• 空間：O(1) —— 僅使用常數額外指針。

示例演示

輸入：1→2→3→4
中點後斷開：1→2 和 3→4
反轉後半：4→3
交替合併：1→4→2→3

總結

本題綜合考察鏈表基本操作：找中點、反轉、合併。掌握這三個核心步驟的邊界條件（空鏈表、單節點、雙節點）是寫出健壯代碼的關鍵。