回文链表

这是一道围绕链表展开的高频练习。建议先掌握「快慢指针 + 反转后半段」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。

链表

题目分析

这道题表面上是在处理「回文链表」，但先要想清楚题目到底让你返回什么，以及过程中哪些约束必须一直满足。从题型上看，它主要在考链表这些能力。先别急着写代码，先把题目要求翻译成人话，明确结果是什么、约束是什么、过程里要持续维护什么。只有先把题目要求翻译成人话，后面的推荐代码才是在实现思路，而不是直接给答案。

接下来怎么看推荐代码：带着这个理解再看推荐代码时，重点观察这条主线：先用快慢指针找到链表中点，再反转后半段并与前半段逐个比较。

推荐代码

推荐解法：快慢指针 + 反转后半段

时间复杂度： O(n)

空间复杂度： O(1)

核心思路：先用快慢指针找到链表中点，再反转后半段并与前半段逐个比较。

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

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

        ListNode secondHalf = reverse(slow);
        ListNode firstHalf = head;

        while (secondHalf != null) {
            if (firstHalf.val != secondHalf.val) {
                return false;
            }
            firstHalf = firstHalf.next;
            secondHalf = secondHalf.next;
        }

        return true;
    }

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

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

        return prev;
    }
}

结构化讲解

面试时怎么讲

开场思路

这题我会在 O(1) 额外空间内做，方法是找中点后反转后半段。

核心过程

先用快慢指针找到链表中点。
从中点开始原地反转后半段。
再让一个指针从头出发，另一个从反转后的后半段出发逐个比较。
如果都相等就是回文，否则不是。

复杂度总结

时间复杂度 O(n)，空间复杂度 O(1)。

面试补一句：这题的面试亮点在于把链表的“对称比较”转成同向扫描。

核心思路

链表回文的关键不是比较，而是如何在 O(1) 额外空间下拿到“对称位置”。标准做法是定位中点后原地反转后半段，让比较变成线性同步扫描。

步骤讲解

快慢指针找中点

快指针一次走两步，慢指针一次走一步，慢指针最终停在中间附近。

为什么这样做：中点把链表拆成前后两半，是后续反转的起点。

对应代码提示：while (fast != null && fast.next != null) { ... }

原地反转后半段链表

从慢指针开始反转链表，使后半段顺序颠倒。

为什么这样做：反转后，前半段和后半段就能从头到尾一一比较。

对应代码提示：ListNode second = reverse(slow);

逐个比较两半链表

同时移动两个指针，只要值不同就返回 false。

为什么这样做：回文要求对称位置的值完全一致。

对应代码提示：while (second != null) { ... }

易错点

奇数长度时中点处理混乱

如果不清楚慢指针落点，可能把中间节点也拿去比较。

正确理解：直接从慢指针开始反转，比较时以后半段长度为准即可。

反转链表时断链

指针更新顺序不当会丢失后续节点。

正确理解：按 next -> reverse link -> advance 的顺序写标准反转模板。

复杂度与适用判断

时间复杂度：O(n)

空间复杂度：O(1)

比其他方案更好在哪里：比用数组存值再双指针比较更省空间。

适用判断：链表题既要比较对称位置又限制额外空间时，通常会用到中点和反转。

额外提醒

反转后半段以后，比较过程就和数组双指针一样直观。