LeetCode 面试题 02.06. 回文链表

2023-10-17 HGNULB 约 11 分钟

文章信息 4 个分类 4 个标签

分类

LeetCode 简单已掌握程序员面试金典（第 6 版）

题目描述

✅ 面试题 02.06. 回文链表

题意分析

题目目标：判断一个单向链表的值序列是否构成回文，是返回 true，否返回 false。

核心约束：链表是单向的，只能从头往后走，没法像数组那样两端往中间夹——这是全题的难点来源。同时面试里这题几乎必定跟一句「能不能 $O(1)$ 空间」，所以「先倒进数组再双指针」虽然正确，却只是热身答案。

边界处理：空链表和单节点链表都算回文；节点数为偶数时两半等长，为奇数时中间那个节点不参与比较；数值可能为负也可能重复，比较必须逐个进行而不能靠求和、异或之类的哈希手段。

实现取舍：三条路——倒进数组双指针（$O(n)$ 空间）、用栈存前半段（$O(n/2)$ 空间）、找中点后反转后半段再逐一比对（$O(1)$ 空间）。最后一种是面试官想看的，它把「回文判断」拆成了三个独立的链表基本功：快慢指针找中点、原地反转、双链表并行比较。

解法：双指针收缩边界

核心思路

最直白的做法是遍历一遍把值倒进 ArrayList，然后左右指针向中间夹。这在数组上是标准答案，但在链表题里它绕开了考点——面试官想看的是你能不能只用指针操作解决问题，而不是把链表退化成数组。

瓶颈是什么？回文判断本质上需要「第 $i$ 个」和「倒数第 $i$ 个」同时可访问，而单链表只能正向走。数组解法用额外空间买到了随机访问，栈解法用额外空间买到了逆序访问。

关键观察：既然逆序访问是刚需，那就把后半段链表原地反转，让它变得可以从尾部往中间正向走。反转之后，前半段从头走、反转后的后半段也从头走，两条链并行推进，逐个比较即可。整个过程只动指针不建结构，空间降到 $O(1)$。

于是有三段清晰的不变量。第一段（找中点）：快指针每步走 2、慢指针每步走 1，且快指针初始就领先一格（fast = head.next），循环结束时 slow 恰好停在前半段的最后一个节点上——偶数长度时 slow 是第 $n/2$ 个节点，奇数长度时 slow 是第 $(n+1)/2$ 个节点，也就是正中间那个。第二段（反转）：把 slow.next 开始的后半段头插到哑结点上，得到一条逆序链，同时 slow.next = null 把前半段截断，两条链彻底独立。第三段（比较）：以反转后的链为循环控制条件，因为它的长度总是不超过前半段——奇数长度时前半段比它多一个（正中间那个节点），这个节点在回文判断中本就该被跳过，用短链控制循环正好自动跳过它。

特别说明为什么 fast 要从 head.next 起步而不是 head。若从 head 起步，偶数长度时 slow 会停在后半段的第一个节点上，切割位置就偏了一格。让 fast 先领先一格，等价于把「向上取整」改成「向下取整」，正好把切点落在前半段末尾。

解题步骤

第一步：head == null 直接返回 true。 为什么必须先判：后面要访问 head.next，空链表会直接空指针；语义上空链表也确实是回文。

第二步：slow = head、fast = head.next，当 fast != null && fast.next != null 时 slow 走一步、fast 走两步。 为什么循环条件要同时判两个：fast 每轮要走两步，只判 fast != null 的话 fast.next.next 会在最后一轮爆掉。为什么这样能停在前半段末尾：fast 领先一格且速度是两倍，fast 走到尽头时 slow 恰好走了一半路程。

第三步：p = slow.next，然后 slow.next = null。 为什么先取后断：断链之后就再也拿不到后半段的头了，顺序反了会丢失整条后半段。为什么要断：不断的话前半段的遍历会一路走进已经被反转的后半段，形成环或越界。

第四步：用哑结点做头插法反转 p 这条链。 循环体里先 next = p.next 保存后继，再 p.next = dummy.next 把当前节点挂到已反转部分的前面，接着 dummy.next = p 更新头，最后 p = next 前进。为什么必须先保存 next：p.next 马上要被覆盖，不先存下来就断了通往剩余节点的唯一通路。为什么用哑结点：省掉「第一个节点的 next 要置空」这个特判，dummy.next 初始为 null 天然充当了新链的尾。

第五步：p = dummy.next，与 head 并行推进，逐个比较 val，不等立即返回 false。 为什么循环条件挂在 p 上而不是 head 上：奇数长度时前半段多出中间那个节点，挂在 p 上会在比完所有该比的节点后自然退出；挂在 head 上则会多走一轮并访问到 null.val。

第六步：循环走完说明每一对都相等，返回 true。

以 head = [1, 2, 3, 2, 1]（奇数长度）走一遍：初始 slow 指向 1（下标 0），fast 指向 2（下标 1）。

第 1 轮：fast（下标 1）非空且 fast.next（下标 2）非空，slow 前进到下标 1（值 2），fast 前进两步到下标 3（值 2）。第 2 轮：fast（下标 3）非空且 fast.next（下标 4）非空，slow 前进到下标 2（值 3），fast 前进两步到下标 5，即 null。此时循环条件 fast != null 不成立，退出。slow 停在下标 2，也就是正中间那个 3——符合不变量。

切割：p = slow.next 指向下标 3（值 2），slow.next = null，前半段变成 1 → 2 → 3，后半段是 2 → 1。

反转后半段：p 指向值 2 的节点，next 存下值 1 的节点，p.next = dummy.next = null，dummy.next = p，此时新链是 2；p 移到值 1 的节点，next 存 null，p.next = dummy.next（值 2 的节点），dummy.next = p，新链变成 1 → 2；p = null 退出。

比较：p = 1 → 2，head = 1 → 2 → 3。第一轮 head.val = 1、p.val = 1，相等，双双前进；第二轮 head.val = 2、p.val = 2，相等，前进后 p 变成 null。循环退出，返回 true。注意前半段那个值为 3 的中间节点从头到尾没参与比较，正是奇数长度下期望的行为。

再以 head = [1, 2] 走一遍偶数的最小情形：slow 指向 1，fast 指向 2，fast.next == null 立刻退出循环，slow 停在下标 0，确实是前半段（只有一个节点）的末尾。切割后前半段是 1、后半段是 2，反转后仍是 2。比较 1 与 2 不等，返回 false，正确。

代码实现

class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null) {
            return true;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode p = slow.next;
        slow.next = null;
        ListNode dummy = new ListNode(0);
        while (p != null) {
            ListNode next = p.next;
            p.next = dummy.next;
            dummy.next = p;
            p = next;
        }
        p = dummy.next;
        while (p != null) {
            if (head.val != p.val) {
                return false;
            }
            head = head.next;
            p = p.next;
        }
        return true;
    }
}

func isPalindrome(head *ListNode) bool {
    if head == nil {
        return true
    }
    slow, fast := head, head.Next
    for fast != nil && fast.Next != nil {
        slow, fast = slow.Next, fast.Next.Next
    }
    p := slow.Next
    slow.Next = nil
    dummy := &ListNode{}
    for p != nil {
        next := p.Next
        p.Next = dummy.Next
        dummy.Next = p
        p = next
    }
    p = dummy.Next
    for p != nil {
        if head.Val != p.Val {
            return false
        }
        head = head.Next
        p = p.Next
    }
    return true
}

复杂度分析

时间复杂度：$O(n)$。凭什么：三个阶段各扫一遍——找中点时快指针走了 $n/2$ 轮、反转后半段走 $n/2$ 个节点、比较最多走 $n/2$ 对，合计是 $n$ 的常数倍，没有任何嵌套循环。

空间复杂度：$O(1)$。凭什么：全程只有 slow、fast、p、next、dummy 五个指针变量，反转是原地改 next 指向而非新建节点，也没有递归栈。

关键点总结

单链表缺少逆序访问能力时，「原地反转一半」是把它补上的标准手段。 这比借助数组或栈更能体现链表基本功，也是本题被反复考的原因。

快慢指针的起点决定了中点的取整方向。 fast = head.next 落在前半段末尾，fast = head 落在后半段开头，两者都对，但必须和后续的切割逻辑配套，不能混着记。

修改 next 之前一定先保存后继。 反转链表的所有变体（92、25、143）都栽在这一步上，形成「存 → 改 → 移」的固定节奏。

哑结点用来消灭「第一个节点」的特判。 凡是要往链头插入的场景，先建 dummy 几乎总能少写一个分支。

比较阶段用短链控制循环，可以自动跳过奇数长度的中间节点。 这类「让循环条件替你处理边界」的技巧比多写一个 if 更不容易错。

面试视角：标准应答节奏是「先说数组解法证明自己会做 → 主动问是否要求 $O(1)$ 空间 → 给出找中点 + 反转 + 比较三段式」。写完之后主动补一句「如果这是线上服务的共享数据结构，破坏性反转是不可接受的，比较完应该再反转回去还原链表」，这句几乎是本题的隐藏加分项。

易错点总结

错误写法：while (fast != null) 少判 fast.next → 用例 [1,2,3]，第二轮 fast 指向下标 2，fast.next 为 null，执行 fast.next.next 抛出空指针异常。

错误写法：fast = head 而不是 head.next，其余不变 → 用例 [1,2]，循环条件 fast != null && fast.next != null 成立一轮，slow 走到下标 1，切割后前半段是 1 → 2、后半段为空，反转结果为空链，比较循环一次都不执行直接返回 true，而正确答案是 false。

错误写法：先 slow.next = null 再 p = slow.next → 用例 [1,2,2,1]，p 拿到的是 null，后半段整个丢失，比较循环空转，任何输入都返回 true。

错误写法：忘记 slow.next = null 不切断前半段 → 用例 [1,2,2,1]，反转后半段后前半段的尾节点仍指向原来的第 3 个节点，而该节点的 next 已被改指，比较时 head 会走进反转后的链里，p 先走完退出循环返回 true，看似正确；换成 [1,2,3,4] 时前半段变成 1 → 2 → 3（3 是反转链的尾），比较 1 与 4 不等返回 false 也碰巧对，但链表结构已被破坏成不可预期的形状，后续任何复用都会出问题。

错误写法：反转循环里漏掉 ListNode next = p.next 直接写 p.next = dummy.next; dummy.next = p; p = p.next; → 用例 [1,2,2,1] 的后半段 2 → 1，第一轮把 p.next 改成 null 后 p = p.next 得到 null，循环立刻结束，反转链只有一个节点，比较时 p 一轮就走完返回 true，[1,2,3,4] 这类非回文也会被判成回文。

错误写法：比较循环写成 while (head != null) → 用例 [1,2,3,2,1]，前半段有 3 个节点而反转链只有 2 个，第三轮访问 p.val 时 p 已是 null，抛出空指针异常。

错误写法：比较时用 head != p 或 head.equals(p) 判断 → 用例 [1,2,2,1]，两条链的节点对象本就不同，恒不相等，直接返回 false；必须比较 val 字段。

错误写法：为省事把 dummy 去掉，写成 ListNode pre = null; 但循环体仍写 p.next = dummy.next 的等价物时忘了同步更新 pre → 用例任意长度大于 2 的链表，反转结果只保留最后一个节点，比较提前结束。

错误写法：用求和或异或代替逐个比较（如判断前后半段和相等） → 用例 [1,2,3,0]，前半段和 3、后半段和 3 相等被判为回文，实际不是。

错误写法：认为空链表应返回 false → 用例 []，期望 true，返回 false 判错。

相似题目

题目	难度	考察点
24. 两两交换链表中的节点	中等	反转的粒度固定为 2 个节点，重点是每对交换后与前驱重新接线
25. K 个一组翻转链表	困难	需要先探测够不够 k 个再决定是否反转，且不足 k 个要保持原序
92. 反转链表 II	中等	只反转指定区间，难点在于记录区间前驱并把三段重新拼接
143. 重排链表	中等	同样是「找中点 + 反转后半段」，但最后一步是交叉合并而非逐个比较
206. 反转链表	简单	纯反转本身，是本题第四步的独立练习
234. 回文链表	简单	主站同题，可用来对照递归写法（用函数调用栈实现逆序访问）的空间代价
LCR 024. 反转链表	简单	反转的迭代与递归两种写法的对比练习
LCR 026. 重排链表	中等	在重排基础上要求还原后链表仍然可遍历，对断链顺序更敏感
LCR 027. 回文链表	简单	同题的专题版，适合用来练「比较完再反转回去」的无损实现
剑指 Offer 24. 反转链表	简单	反转的经典出处，面试常要求当场同时写出迭代与递归两版