LeetCode 234：回文鏈表判斷（遞歸 O(1) 空間）

題目描述

給定單鏈表，判斷是否為回文。進階要求：O(n) 時間、O(1) 空間（不計遞歸棧）。

遞歸後序遍歷解法

利用遞歸到達鏈表末尾，回溯時依次比較頭節點與尾節點。通過引用參數 cur 追蹤前向節點。若所有對應節點值相等則為回文。

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode* cur = head;
        return check(head, cur);
    }

private:
    bool check(ListNode* node, ListNode*& cur) {
        if (!node) return true;
        if (!check(node->next, cur)) return false;
        if (cur->val != node->val) return false;
        cur = cur->next;
        return true;
    }
};

複雜度

• 時間：O(n)，每個節點訪問兩次（遞歸下行與回溯）。
• 空間：O(n) 遞歸棧，若不計棧則 O(1)。