跳到主要内容

LeetCode 234. 回文链表

本节目标

反转链表后半段进行对称比较，并在返回答案前恢复原链表。

查看 LeetCode 原题

题意与边界​

判断单链表从前到后的值序列是否为回文。目标是 O(n) 时间和 O(1) 辅助空间；比较过程中可以临时改动指针，但返回前恢复原链表，使调用者观察不到结构副作用。

中点、反转与恢复​

快慢指针让 slow 停在前半段末尾，再原地反转 slow.next 开始的后半段。从头部和反转后的后半段同步比较，只需以后半段结束为界。无论比较成功还是失败，都把保存的后半段头再次反转并接回 slow.next。

正确性依据​

后半段反转后，其遍历顺序正好对应原序列从尾到中间的顺序。前后两个指针逐项相等，当且仅当原序列关于中心对称。奇数长度的中间节点不参与成对比较，不影响结论；第二次反转是第一次反转的逆操作，因此完整恢复所有连接。

代码实现​

C++17
class Solution {
private:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* cur = head;
        while (cur != nullptr) {
            ListNode* nxt = cur->next;
            cur->next = prev;
            prev = cur;
            cur = nxt;
        }
        return prev;
    }

public:
    bool isPalindrome(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return true;
        }

        ListNode* slow = head;
        ListNode* fast = head;
        while (fast->next != nullptr && fast->next->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }

        ListNode* second = reverseList(slow->next);
        ListNode* right = second;
        ListNode* left = head;
        bool matches = true;
        while (right != nullptr) {
            if (left->val != right->val) {
                matches = false;
                break;
            }
            left = left->next;
            right = right->next;
        }
        slow->next = reverseList(second);
        return matches;
    }
};

复杂度分析​

  • 时间复杂度：O(n)，找中点、两次反转和比较都是线性扫描。
  • 空间复杂度：O(1)，只维护有限个指针。

易错点​

  • 比较失败后直接返回，导致后半段没有恢复。
  • 奇数长度时把中间节点也当成需要配对的元素。
  • 把所有值复制到数组中，虽简单但不满足进阶空间目标。

模式迁移​

“先局部变换、完成判断、再撤销变换”的结构适用于需要暂时重排输入、但又必须保持调用者可观察状态不变的问题。实现时应把恢复步骤放在所有提前退出路径之后统一执行。