LeetCode 234. 回文链表

2026-09-09 HGNULB 约 6 分钟

文章信息 20 个分类 6 个标签

分类

LeetCode CodeTop 简单已解决需复习 50-100 字节跳动微软美团阿里巴巴快手腾讯猿辅导百度滴滴拼多多网易虾皮图森 LeetCode 热题 100

题目描述

✅ 234. 回文链表

题意分析

给定单链表的头节点，判断链表中所有节点值从前往后读和从后往前读是否完全一致，是则返回 true。

判断回文本身不难，难点全在数据结构上：单链表只能从头往后走，既不能随机访问下标，也不能从尾往前退，所以数组里「首尾双指针向中间夹」的做法无法直接套用。

题目在进阶里明确要求 $O(n)$ 时间加 $O(1)$ 空间，这是一个强信号：把节点值全部读进数组再判断虽然可行，但用了 $O(n)$ 额外空间，正是出题人想让你绕开的路径。

边界方面：链表长度至少为 1，空链表和单节点链表天然是回文；长度为奇数时中间那个节点不参与两两配对，怎么处理它是实现的关键细节。

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

核心思路

数组可以用首尾指针判断回文，但会占用 $O(n)$ 空间；单链表又不能从尾部向前遍历。解决办法是先找到中点，再原地反转后半段，使它的遍历方向变成“从原链表尾部走向中间”，随后与前半段同步比较。

快慢指针都从头开始，循环条件使用 fast.next != null && fast.next.next != null，结束时 slow 停在前半段尾部：偶数长度停在左半部分最后一个节点，奇数长度停在中间节点。因此从 slow.next 开始反转，比较循环只需以后半段是否结束为准，中间节点会被自然跳过。

比较时的不变量是：两指针已经走过的节点分别对应原序列两端，且值全部相等；出现不同即可确定不是回文。比较结束后再次反转并接回 slow.next，避免函数悄悄改变调用方的链表结构。

解题步骤

长度小于 2 时直接返回 true。

用快慢指针定位前半段尾节点 slow。

反转 slow.next 开始的后半段，得到从原尾节点出发的新链表。

first 从头、second 从反转后的头同步前进；只要一对值不同就记录 false，后半段走完则比较结束。

再反转后半段并接回 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(n)$。

空间复杂度：$O(1)$。只使用固定数量的指针和一个布尔变量。

关键点总结

反转后半段把“从尾部向前比较”转化为单链表擅长的正向遍历。

快慢指针的循环边界决定 slow 落点，必须与 slow.next 开始反转的约定配套。

比较以后半段结束为准，才能统一处理奇偶长度并跳过中间节点。

面试中应说明链表会被暂时修改；恢复只多一次 $O(n)$ 遍历，却能避免副作用。

易错点总结

使用 fast != null && fast.next != null 却仍从 slow.next 反转：偶数长度时 slow 会落到右半段，导致漏比节点。

反转链表时先改 current.next、后保存后继：会丢失剩余链表。

比较两个节点对象而不是 val：对应位置是不同节点，引用本就不相等。

用 first 是否到尾作为循环条件：奇数长度时会把中间节点纳入比较。

发现不等后直接返回：会跳过恢复步骤，留下被修改的输入链表。

相似题目

题目	难度	考察点
206. 反转链表	简单	三指针迭代反转整条链表，本题的子过程
876. 链表的中间结点	简单	快慢指针找中点，注意落点与本题不同
143. 重排链表	中等	找中点加反转后再交替合并两段
92. 反转链表 II	中等	只反转指定区间，考察边界节点的重接
24. 两两交换链表中的节点	中等	相邻两节点为一组的局部指针交换
25. K 个一组翻转链表	困难	分组反转，不足一组的尾部保持原序
141. 环形链表	简单	快慢指针的另一用途：判环
LCR 027. 回文链表	简单	本题的 LCR 编号版本
LCR 024. 反转链表	简单	206 的 LCR 编号版本
LCR 026. 重排链表	中等	143 的 LCR 编号版本
剑指 Offer 24. 反转链表	简单	206 的剑指 Offer 版本
面试题 02.06. 回文链表	简单	本题的面试金典版本