LeetCode LCR 027. 回文链表

约 8 分钟
文章信息 5 个分类 5 个标签
分类
LeetCode 简单 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
双指针 LCR 栈 链表 递归
目录

题目描述

✅ LCR 027. 回文链表

题意分析

给定一条单链表，判断它的节点值序列是否回文，返回布尔值。这里比较的是值，不是节点身份。

回文的定义是「正着读和倒着读一样」，即第 i 个与倒数第 i 个值相等。数组上用左右双指针相向而行两三行就写完了，但单链表没有随机访问，也拿不到前驱，「倒数第 i 个」这个概念本身就取不到——这是本题唯一的难点。

进阶要求 $O(n)$ 时间与 $O(1)$ 空间。这条约束否掉了两个最直观的做法：把值拷进数组再双指针（$O(n)$ 空间），以及把前半段压栈再与后半段比对（同样 $O(n)$ 空间）。

长度奇偶要区分对待。长度为奇数时正中间那个节点无需参与比较，它跟谁都不冲突；长度为偶数时所有节点都要配对。实现上应该让这两种情况走同一条代码路径。

边界：空链表和单节点链表按定义都是回文，必须返回 true。

解法：双指针收缩边界

核心思路

先看暴力：遍历一遍把所有值放进数组，再用左右下标向中间靠拢逐一比较。$O(n)$ 时间但 $O(n)$ 空间，瓶颈非常清楚——数组的唯一作用是提供「反向读取」的能力。

既然只需要反向读，那就没必要保留全部数据：把链表的后半段就地反转，反向读取立刻变成正向读取，两半从各自的头开始同步前进逐位比较即可。这样一份额外空间都不需要。

于是解法拆成三步：定位前半段的末节点、反转后半段并断开、两段同步比对。

第一步的不变量是「fast 走过的步数恒为 slow 的两倍」。这里 fast 从 head.next 起步而不是从 head 起步，效果是让 slow 的落点整体左移半格：长度为偶数时 slow 停在左半段的最后一个节点，长度为奇数时 slow 停在正中间那个节点。两种情况下 slow.next 之后的部分长度都恰好等于 n / 2 向下取整，正中间那个节点被留在了前半段里，自动被排除出比较范围。

第二步反转维持链表反转的标准不变量：pre 段已反转、cur 段保持原向、两段断开；反转前先执行 slow.next = null 把两半彻底切开，否则比对时会顺着旧指针绕回去。

第三步的循环以后半段（较短的那一段）走完为终止条件。因为前半段长度不小于后半段，用 pre != null 控制循环就能保证 head 一侧永远取得到值，不会空指针；一旦发现某一对不等立即返回 false，走完全部配对则返回 true。

解题步骤

  • 提前返回：head == null || head.next == null 时直接返回 true。空链表与单节点按定义就是回文，提前挡掉还能保证后续 slow.next 一定存在。
  • 定位中点：slow = head、fast = head.next，循环条件 fast != null && fast.next != null。fast 的起点比 slow 靠后一格，这是让 slow 停在「前半段末尾」而非「后半段开头」的关键；两个判空缺一不可，因为 fast 一次跳两格。
  • 切断并反转：先 cur = slow.next 取到后半段入口，再 slow.next = null 断开，然后用 pre、cur、t 三指针原地反转。取入口与断开的顺序不能反，先断就找不到后半段了。
  • 同步比对：while (pre != null)，逐位比较 pre.val 与 head.val，不等立即返回 false，相等则两个指针各走一步。循环条件用 pre（后半段，较短）而不是 head，这样长度为奇数时中间那个多出来的节点自然不参与比较。
  • 返回 true：所有配对都相等。

以 1 → 2 → 3 → 2 → 1 走一遍。定位中点：slow = 1、fast = 2（第二个节点）；fast.next 是 3 非空，推进后 slow = 2、fast 跳到第四个节点 2；此时 fast 非空但 fast.next 是最后一个节点 1 非空，再推进 slow = 3（正中间）、fast = 1.next = null；循环退出，slow 停在正中间的 3。

切断：cur 指向第四个节点，得到前半段 1 → 2 → 3 与后半段 2 → 1。反转后半段得到 1 → 2，pre 指向值为 1 的那个节点。

比对：pre.val = 1 与 head.val = 1 相等，各走一步；pre.val = 2 与 head.val = 2 相等，各走一步；此时 pre 变为空，循环退出，返回 true。注意正中间的 3 从头到尾没被比较过，正是我们想要的。

再看反例 1 → 2 → 3：slow = 1、fast = 2，fast.next 是 3 非空，推进后 slow = 2、fast = 3.next = null，退出。切断得前半段 1 → 2、后半段 3，反转仍是 3。比对第一轮 3 与 1 不等，立即返回 false，正确。

代码实现

class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        // fast 起点比 slow 靠后一格，使 slow 停在前半段末尾。
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 先取后半段入口，再断开，否则后半段丢失。
        ListNode cur = slow.next;
        slow.next = null;
        ListNode pre = null;
        while (cur != null) {
            ListNode t = cur.next;
            cur.next = pre;
            pre = cur;
            cur = t;
        }
        // 用较短的后半段控制循环，奇数长度时中间节点自动跳过。
        while (pre != null) {
            if (pre.val != head.val) {
                return false;
            }
            pre = pre.next;
            head = head.next;
        }
        return true;
    }
}

func isPalindrome(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return true
    }
    // fast 起点比 slow 靠后一格，使 slow 停在前半段末尾。
    slow, fast := head, head.Next
    for fast != nil && fast.Next != nil {
        slow, fast = slow.Next, fast.Next.Next
    }
    // 先取后半段入口，再断开，否则后半段丢失。
    var pre *ListNode
    cur := slow.Next
    slow.Next = nil
    for cur != nil {
        t := cur.Next
        cur.Next = pre
        pre = cur
        cur = t
    }
    // 用较短的后半段控制循环，奇数长度时中间节点自动跳过。
    for pre != nil {
        if pre.Val != head.Val {
            return false
        }
        pre, head = pre.Next, head.Next
    }
    return true
}

复杂度分析

  • 时间复杂度：$O(n)$。定位中点扫半条链，反转扫后半条，比对最多再扫半条，三段线性且互不嵌套，循环体内只有指针赋值与一次整数比较。
  • 空间复杂度：$O(1)$。全程只用了 slow、fast、pre、cur、t 这几个指针，没有数组、没有栈、也没有递归；这正是它相对「拷进数组」和「前半段压栈」两种解法的核心优势。

关键点总结

  • 链表需要反向读取又不许开额外空间时，就地反转是把「倒着读」变成「正着读」的通用手段，这条思路可以直接迁移到重排、求孪生和等题。
  • 让 fast 从 head.next 起步，就把奇偶两种长度统一成「后半段长度为 $\lfloor n/2 \rfloor$」，中间节点自动被排除，省掉了奇偶分支。
  • 比对循环要用较短的那一段作条件，长的那一段才不会越界；哪一段短要在切分时就想清楚，而不是靠事后判空补救。
  • 切断两段是独立且必要的一步，不切断会让比对顺着旧指针绕回前半段，得到看似正确实则偶然的结果。
  • 面试视角：先说数组解法确认思路，再指出进阶要求 $O(1)$ 空间，然后给出「找中点 + 反转 + 比对」。面试官常追问「这个方法破坏了原链表怎么办」，标准回答是比对结束后把后半段再反转一次接回去，并说明这在多线程读取场景下才是刚需——能主动提到这一点通常是加分项。

易错点总结

  • fast 与 slow 都从 head 起步：1 → 2 时 slow 会停在第二个节点，slow.next 为空，后半段为空，比对循环一次不进直接返回 true，而正确答案是 false。
  • 先执行 slow.next = null 再取 cur：1 → 2 → 2 → 1 拿到的后半段为空，比对循环不进入，任何输入都返回 true。
  • 完全不断开两段：反转后前半段末节点仍指向后半段旧尾，1 → 2 → 3 的比对会顺着残留指针继续走，结果不可预测。
  • 比对循环写成 while (head != null)：1 → 2 → 3 → 2 → 1 中 pre 先走空，再取 pre.val 触发空指针异常。
  • 循环条件只写 fast.next != null：1 → 2 → 2 → 1 走到 fast 为空时再取 fast.next 直接空指针。
  • 用节点身份而非节点值比较：1 → 2 → 1 中前后两个节点是不同对象，按引用比较会返回 false，而正确答案是 true。
  • 漏掉 head == null 的提前返回：空链表进入 head.next 就空指针异常。
  • 反转子过程忘记暂存 cur.next：后半段 2 → 1 第一轮就断成孤立节点，1 → 2 → 2 → 1 会少比一位，非回文输入可能被误判为回文。
  • 把值拷进数组再双指针并宣称 $O(1)$ 空间：数组长度随 n 增长，实际是 $O(n)$，进阶要求没有满足。

相似题目

题目 难度 考察点
234. 回文链表 简单 与本题同题，可直接套用「找中点 + 反转 + 比对」
面试题 02.06. 回文链表 简单 与本题同题，可直接套用
206. 反转链表 简单 只做本题的第二步，是整套解法的基础零件
143. 重排链表 中等 前两步完全相同，第三步把「比对」换成「交替缝合」
2130. 链表最大孪生和 中等 前两步相同，第三步改成对应位置求和并取最大值
面试题 01.04. 回文排列 简单 判断能否重排成回文，只需统计奇数次字符个数，与顺序无关
125. 验证回文串 简单 载体换成字符串，可随机访问，直接左右双指针并跳过非字母数字字符