234. 回文链表

难度：🟢 Easy | 标签：链表、双指针 | 状态：⬜ LeetCode 链接

思路

O(1) 空间法：

1. 快慢指针找中点
2. 反转后半段
3. 从两端比较

代码

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode *slow = head, *fast = head;
        while (fast && fast->next) { slow = slow->next; fast = fast->next->next; }

        ListNode *prev = nullptr, *cur = slow;
        while (cur) { auto nxt = cur->next; cur->next = prev; prev = cur; cur = nxt; }

        for (ListNode *a = head, *b = prev; b; a = a->next, b = b->next)
            if (a->val != b->val) return false;
        return true;
    }
};

复杂度

• 时间 O(n)，空间 O(1)

易错 / 回顾

• 快慢指针：奇数节点 slow 落中间，偶数节点落后半段第一个，都不影响
• 比较循环用 b 终止（后半段更短或等长），不要用 a
• 严格点应该把链表还原（恢复原链表结构），面试可口头提一下