LeetCode 234. 回文链表

约 6 分钟
文章信息 21 个分类 4 个标签
分类
LeetCode CodeTop 简单 已解决 需复习 50-100 LeetCode 热题 100 腾讯 字节 阿里 华为 微软 美团 拼多多 百度 网易 快手 滴滴 虾皮 猿辅导 图森
标签
双指针 栈 链表 递归

题目描述

✅ 234. 回文链表

image-20260928193840825

image-20260928193840826

题意分析

判断链表节点值组成的序列是否为回文，也就是从头向后读和从尾向前读完全相同。比较的是对称位置的值，不是节点对象是否相同；奇数长度时，中间节点不需要与其他节点配对。

单链表无法通过当前节点直接走向前驱。题目的进阶要求是线性时间、常数额外空间，因此不能把所有值复制到数组或压入栈后再倒序比较。下面的实现会暂时调整后半段指针，并在返回前恢复链表。

解法：快慢指针 + 反转后半链表

核心思路

[!blue]

回文需要比较第一项与最后一项、第二项与倒数第二项，依次向中间靠近。只把后半段反转，就能让它按原链表从尾向前的顺序出现；随后两个指针都沿 next 向前移动，就可以完成首尾配对。

先用快慢指针找分界。两者从头出发，快指针每次走两步，但仅在它后面仍有两个节点时继续。这使偶数长度时 slow 停在前半段尾部，奇数长度时停在中间节点。统一从 slow.next 开始反转，就恰好取到需要配对的后半段，奇数长度的中点自然被排除。

反转时，用 previous 表示已经反好的部分，用 current 表示尚未处理的节点。先保存原后继，再把当前节点指向 previous，最后推进两个指针，这样不会丢失未处理部分。

让 first 从原头节点出发，second 从反转后的头节点出发，逐对比较值。比较次数以后半段为准：它恰好包含所有需要配对的节点；如果都相等就是回文，只要一对不同就可以确定失败。

另外保存后半段的头节点 secondHead，比较完后再次反转并接回 slow.next。即使发现不等，也只记录失败并退出比较，恢复之后才返回，确保两种结果都不留下链表结构变化。

解题步骤

  1. 空链表或只有一个节点时直接返回 true。
  2. 从头启动快慢指针，在 fast.next 和 fast.next.next 均存在时移动，找到约定的分界节点 slow。
  3. 反转 slow.next 开始的后半段，并保存反转后的头节点 secondHead。
  4. 从原链头和 secondHead 同时前进，直到后半段结束；遇到值不相等就记录失败并结束比较。
  5. 用 secondHead 再次反转后半段，将结果接回 slow.next，最后返回记录的比较结果。

代码实现

class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }

        ListNode slow = head;
        ListNode fast = head;

        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // 从中点之后反转，奇数长度的中间节点不参与配对。
        ListNode secondHead = reverse(slow.next);
        ListNode first = head;
        ListNode second = secondHead;
        boolean palindrome = true;

        while (second != null) {
            if (first.val != second.val) {
                palindrome = false;
                break;
            }

            first = first.next;
            second = second.next;
        }

        // 成功或失败都要恢复后半段，再返回比较结果。
        slow.next = reverse(secondHead);

        return palindrome;
    }

    private ListNode reverse(ListNode head) {
        ListNode previous = null;
        ListNode current = head;

        while (current != null) {
            ListNode next = current.next;

            current.next = previous;
            previous = current;
            current = next;
        }

        return previous;
    }
}

func isPalindrome(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return true
    }

    slow, fast := head, head
    for fast.Next != nil && fast.Next.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }

    // 从中点之后反转，奇数长度的中间节点不参与配对。
    secondHead := reverseList(slow.Next)
    first, second := head, secondHead
    palindrome := true

    for second != nil {
        if first.Val != second.Val {
            palindrome = false
            break
        }
        first = first.Next
        second = second.Next
    }

    // 成功或失败都要恢复后半段，再返回比较结果。
    slow.Next = reverseList(secondHead)
    return palindrome
}

func reverseList(head *ListNode) *ListNode {
    var previous *ListNode
    current := head

    for current != nil {
        next := current.Next
        current.Next = previous
        previous = current
        current = next
    }
    return previous
}

复杂度分析

  • 时间复杂度：$O(n)$，找中点、反转、比较和恢复只是常数次线性遍历。
  • 空间复杂度：$O(1)$。只使用固定数量的指针和一个布尔变量。

关键点总结

[!green]

  • 反转后半段只是为了改变遍历顺序，让单链表也能按首尾对应关系比较。
  • 中点定位、反转起点与比较长度必须配套，才能同时覆盖奇偶长度。
  • 保存后半段入口，并让恢复操作位于所有比较结果之后，避免提前返回破坏输入。

易错点总结

[!yellow]

  • 改用 fast != null && fast.next != null 找中点，却仍从 slow.next 反转，会在偶数长度时多跳过一个节点，漏掉一组比较。
  • 反转时先改后继、后保存原后继，会丢失尚未处理的链表部分。
  • 比较节点引用而不是节点值，会把数值相等的对称位置误判为不同。
  • 以第一段走到末尾作为比较终点，会在奇数长度时继续访问后半段的空指针；应以后半段是否结束为准。
  • 不相等时直接返回，会跳过恢复；拿已经移动过的 second 去恢复，也会丢失后半段入口。

相似题目

题目 难度 关联与区别
2130. 链表最大孪生和 中等 同样把链表首尾位置对齐，原题求孪生和最大值，本题比较对应值是否相等。
206. 反转链表 简单 原地反转后半段是O1空间比较的关键子过程。
143. 重排链表 中等 拆分链表后反转并重新连接；本题反转后半段后比较对称值，该题从中点拆分并交替合并首尾。
92. 反转链表 II 中等 拆分链表后反转并重新连接；本题反转后半段后比较对称值，该题只反转指定区间。
25. K 个一组翻转链表 困难 拆分链表后反转并重新连接；本题反转后半段后比较对称值，该题按固定长度分组反转。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/54516872
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！