LeetCode LCR 027. 回文链表

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

题目描述

✅ LCR 027. 回文链表

image-20260928235120530

image-20260928235120531

题意分析

判断单链表的节点值从前往后与从后往前是否相同，返回布尔值。这里比较的是对应节点的值，不要求两侧节点是同一个对象。

要用线性时间、常数额外空间完成。奇数长度的中间值无需配对，偶数长度则全部成对。下面的实现会断开并反转输入后半段，不负责恢复原连接；空链表和单节点直接视为回文。

解法：反转后半段再比较

核心思路

[!blue]

要比较首尾对应值，必须能从原尾部向前访问。复制到数组或压栈会增加线性空间，原地反转后半段则能直接把这种逆向访问变成顺向访问。

先定位前半段末尾。这里 slow 从头开始，fast 从头的后继开始，每轮分别前进一格、两格。两个起点有一格偏移，因此 slow 在偶数长度时停于左中点，奇数长度时停于正中点；它后面恰好有 floor(n/2) 个节点。

保存 slow.next 后，将这个连接置空并反转后半段。pre 最终指向原尾节点，沿它前进依次访问原倒数第一、第二个节点；从 head 前进则依次访问原第一、第二个节点，正好逐对比较。

后半段长度固定为 floor(n/2)，用它控制比较循环，就会检查全部需要配对的位置，又不会访问奇数链中间那一个。任一对值不同就返回 false，全部配对相同才返回 true。

显式断链是当前实现的分段方式，并非所有反转比较写法都必须断链才正确。这里真正需要保持的是两个访问序列与原首尾位置对应，且比较只进行后半段长度次。

解题步骤

  1. 空链或单节点直接返回 true。
  2. 令 slow = head、fast = head.next，用一倍、两倍速度找到前段末尾。
  3. 保存后段入口，断开两段，再迭代反转后段。
  4. 从原头与反转后段头同步扫描，以后段是否结束控制循环。
  5. 值不同返回 false，所有对应值相同则返回 true。

代码实现

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)$，只维护固定数量的指针。

关键点总结

[!green]

  • 后半段反转后，与前半段同步访问就能逐对比较原首尾值。
  • 快指针提前一格起步，让后段统一有 floor(n/2) 个节点。
  • 以后段控制比较，奇数长度的中点自动排除。
  • 该实现会改变输入结构，返回真假都不会自动恢复。

易错点总结

[!yellow]

  • 不同快指针起点对应不同中点，不能照搬另一种切分方式的结论。
  • 比较循环由较短后段控制，用前段控制可能在奇数长度时读到空后段。
  • 比较节点引用而非值，会把本来值序列回文的链误判为不回文。
  • 保存后段入口必须在断链之前，反转每个节点也要先保存旧后继。
  • 若另有保持输入的要求，必须保存连接点，在比较结束后反转接回；当前实现不承担该要求。

相似题目

题目 难度 关联与区别
2130. 链表最大孪生和 中等 同样把链表首尾位置对齐，原题求孪生和最大值，本题比较对应值是否相等。
206. 反转链表 简单 原地反转后半段是O1空间比较的关键子过程。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/18931886
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！