LeetCode Palindrome Linked List：O(1) 空間判斷回文鏈表

題目簡介

給定一個單鏈表，判斷是否為回文結構。要求時間 O(n)，空間 O(1)。

解題思路

單鏈表無法反向遍歷，解法是將前半部分鏈表反轉，再與後半部分比較：

1. 用快慢指針找到中點（slow 指向後半部分頭節點）。
2. 反轉前半部分鏈表（頭插法）。
3. 同時遍歷反轉後的前半部分和後半部分，比較節點值。
4. 若長度為奇數，slow 再前進一步跳過中間節點。
5. 全部匹配則為回文。

代碼實現

class Solution {
public:
    ListNode* reverseHalf(ListNode* head) {
        ListNode *fast = head, *slow = head;
        while (fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
        }
        ListNode dummy(0);
        dummy.next = head;
        ListNode *sec = head, *fir = head->next;
        while (fir != slow) {
            sec->next = fir->next;
            fir->next = dummy.next;
            dummy.next = fir;
            fir = sec->next;
        }
        return dummy.next;
    }

    bool isPalindrome(ListNode* head) {
        int len = 0;
        for (ListNode* p = head; p; p = p->next) len++;
        if (len < 2) return true;
        ListNode* rev = reverseHalf(head);
        ListNode *fast = rev, *slow = rev;
        while (fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
        }
        fast = rev;
        if (len % 2) slow = slow->next;
        while (slow) {
            if (fast->val != slow->val) return false;
            fast = fast->next;
            slow = slow->next;
        }
        return true;
    }
};

複雜度分析

時間 O(n)，空間 O(1)，滿足題目要求。