LeetCode 234. 回文鏈表：原地反轉後半部 O(n) 時間 O(1) 空間解法

LeetCode 234. 回文鏈表：原地反轉後半部 O(n) 時間 O(1) 空間解法

判斷單鏈表是否為回文結構。進階要求 O(n) 時間、O(1) 空間。本文提供**快慢指針找中點 + 原地反轉後半部 + 雙指針比較 + 可選恢復鏈表**的完美解法，詳細講解奇偶長度處理、反轉邏輯與邊界條件。

算法三步曲

1. 快慢指針找中點：`slow` 走 1 步，`fast` 走 2 步。`fast` 到達末尾時，`slow` 在中點（奇數長度）或中間偏右（偶數長度）。
2. 原地反轉後半部：從 `slow` 開始反轉，得到反轉後的頭指針 `head2`。
3. 雙指針比較：`p=head`、`q=head2` 同步前進比較值。全等則回文。
4. （可選）恢復鏈表：再次反轉後半部接回，保持原結構（面試加分項）。

C 語言完整實現

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool isPalindrome(struct ListNode* head) {
    if (!head || !head->next) return true; // 空或單節點

    // 1. 快慢指針找中點
    struct ListNode *slow = head, *fast = head;
    while (fast->next && fast->next->next) { // 讓 slow 停在中間偏左（偶數）或正中（奇數）
        slow = slow->next;
        fast = fast->next->next;
    }

    // 2. 反轉後半部：從 slow->next 開始
    struct ListNode *prev = NULL, *curr = slow->next;
    slow->next = NULL; // 斷開前半部，便於比較與恢復
    while (curr) {
        struct ListNode *next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    struct ListNode *head2 = prev; // 反轉後的頭

    // 3. 比較前半部與反轉後的後半部
    struct ListNode *p = head, *q = head2;
    bool result = true;
    while (q) { // 只需遍歷後半部（較短或等長）
        if (p->val != q->val) {
            result = false;
            break;
        }
        p = p->next;
        q = q->next;
    }

    // 4. 可選：恢復鏈表（面試加分，LeetCode 不要求）
    // 再次反轉 head2 接回 slow->next
    curr = head2; prev = NULL;
    while (curr) {
        struct ListNode *next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    slow->next = prev;

    return result;
}

關鍵細節深度解析

快慢指針停止條件

while (fast->next && fast->next->next)

• 長度 4 (1-2-3-4)：`slow` 停在 2，`fast` 停在 3（倒數第二）。後半部 3-4 反轉為 4-3，比較 1-2 vs 4-3。
• 長度 5 (1-2-3-4-5)：`slow` 停在 3，`fast` 停在 5（尾）。後半部 4-5 反轉為 5-4，比較 1-2-3 vs 5-4。**中間節點 3 不參與比較**，因 `slow->next` 從 4 開始反轉。

反轉邏輯標準三指針

prev = NULL; curr = start;
while (curr) {
    next = curr->next;
    curr->next = prev;
    prev = curr;
    curr = next;
}
new_head = prev;

斷開前半部 `slow->next = NULL` 的作用

• 比較時 `p` 遍歷前半部自然在 `NULL` 停止，無需額外長度判斷。
• 恢復時作為反轉後半部的新尾連接點。

複雜度分析

• 時間：O(n) —— 找中點 n/2、反轉 n/2、比較 n/2、恢復 n/2，總計 2n ≈ O(n)。
• 空間：O(1) —— 僅常數指針變量。

測試用例

常見錯誤避坑

1. **快慢指針條件寫錯**：用 `fast && fast->next` 導致偶數長度 `slow` 停在中間偏右，後半部包含中間節點，比較邏輯需額外處理。
2. **未斷開前半部**：比較時 `p` 會進入原後半部（現已反轉），導致比較長度錯誤或死循環。
3. **反轉起點錯**：從 `slow` 而非 `slow->next` 開始反轉，會把中間節點納入後半部（奇數長度）。
4. **忘記恢復鏈表**：面試若要求「保持原結構」，不恢復扣分。LeetCode 不檢查結構修改。

總結

回文鏈表判斷是**快慢指針 + 原地反轉**組合拳的經典考點。關鍵在於：快慢指針停止條件控制 `slow` 位置、反轉起點從 `slow->next` 開始、斷開前半部簡化比較邏輯、可選恢復體現工程素養。熟練掌握此模板，可秒殺「鏈表重排序 (LeetCode 143)」、「判斷鏈表是否為迴文」等變體題。