如何判断一个单链表是否为回文链表？

简化版

最优解 O(1) 空间三步走：快慢指针找中点 → 反转后半段 → 从两头向中间逐个比对。前半段从头走、后半段从反转后的尾走，值一路相等就是回文。比完可以再把后半段反转回去还原链表。时间 O(n)、空间 O(1)。

详细版

单链表不能像数组那样从两端往中间夹（没有 prev 往回走），所以要想 O(1) 空间判回文，得先把「后半段反转」制造出一个能从尾往前走的链。

boolean isPalindrome(ListNode head) {
    if (head == null || head.next == null) return true;
    // 1. 快慢指针找中点（slow 停在前半段末尾/中间）
    ListNode slow = head, fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next; fast = fast.next.next;
    }
    // 2. 反转后半段（slow.next 起）
    ListNode second = reverse(slow.next);
    // 3. 双指针比对
    ListNode p1 = head, p2 = second;
    boolean ok = true;
    while (p2 != null) {
        if (p1.val != p2.val) { ok = false; break; }
        p1 = p1.next; p2 = p2.next;
    }
    slow.next = reverse(second);   // 可选：还原链表
    return ok;
}
ListNode reverse(ListNode h) {
    ListNode prev = null;
    while (h != null) { ListNode nx = h.next; h.next = prev; prev = h; h = nx; }
    return prev;
}

完整版教学

一、为什么不能直接双指针夹

数组判回文很简单：左右两个指针往中间靠，比 a[l] 和 a[r]。但单链表只能从头往后走，没有 prev 指针，右指针没法往左移动。所以必须想办法「制造出一个能反向走的结构」——要么额外存值（O(n) 空间），要么原地反转后半段（O(1) 空间）。

二、朴素解法：借助额外空间

拷进数组/列表：遍历链表把值全放进 ArrayList，再用数组的双指针夹着比。O(n) 时间、O(n) 空间，最好写。
用栈：把后半段（或全部）压栈，再一边出栈一边和前半段比。栈的 LIFO 天然实现「反向」。

面试能先说这个证明思路清晰，再给出 O(1) 空间的进阶解。

三、O(1) 空间三步法详解

找中点：快指针一次走两步、慢指针一步，快指针到尾时慢指针在中间。用 fast.next 和 fast.next.next 做条件能让 slow 停在「前半段的最后一个节点」，方便把 slow.next 之后当后半段。
反转后半段：标准的链表反转，把后半段变成从原尾节点往回的链。
对比：一个指针从 head（前半段头）、一个从反转后的后半段头，同步向中间推进，逐个比值。后半段较短或等长，以 p2 != null 为界比完即可（奇数长度时正中间那个不用比）。

四、奇偶长度的处理

偶数个节点（如 1→2→2→1）：前后两半等长，比对到 p2 走完即可。
奇数个节点（如 1→2→3→2→1）：正中间的 3 是对称轴，不需要比较。用上面的快慢指针写法，中点会被划到前半段，后半段更短，while (p2 != null) 自然跳过中间节点，无需特判。

五、要不要还原链表

反转后半段破坏了原链表结构。如果调用方之后还要用这个链表，应当在比完后再反转一次后半段接回去（代码里 slow.next = reverse(second)）。面试中主动提这一点是加分项——说明你考虑到了副作用。

解法	时间	额外空间	是否修改链表
拷贝到数组后双指针	O(n)	O(n)	不修改
栈保存后半段/全部节点值	O(n)	O(n)	不修改
找中点 + 反转后半段	O(n)	O(1)	会修改，最好还原

具体例子：1→2→3→2→1 中，快慢指针让 slow 停在 3，反转 slow.next 得到 1→2，然后用 head 的 1→2 与反转后的 1→2 比对。中间的 3 是对称轴，不需要参与比较。

回文链表 O(1) 空间解法的代价是“临时改链”。如果面试官关心副作用，记得说会把后半段再反转接回去。

六、常见误区与追问

误区：单链表可以像数组一样左右夹逼。 单链表没有前驱指针，右侧不能往左走，必须借助额外空间或反转后半段。
误区：奇数长度必须单独删除中间节点。 用前半段末尾作为 slow 时，后半段从 slow.next 开始，中间节点自然跳过。
误区：比对时应该循环到两个指针都为空。 后半段长度小于或等于前半段，通常以 p2 != null 为准。
追问：为什么要还原链表？ 如果函数调用者还要继续使用原链表结构，不还原会留下被反转的后半段。
追问：能否用递归判断回文？ 可以借助递归栈模拟后序比较，但空间仍是 O(n)，不如 O(1) 的反转后半段。
追问：空链表和单节点是否是回文？ 通常认为是回文，因为没有任何一对不相等的对称元素。

八、伪代码与不变量

数据结构题最好把操作过程写成伪代码，因为指针、索引或状态变化一旦说不清，就容易在边界用例上出错。以如何判断一个单链表是否为回文链表？为例，可以先固定不变量，再解释每一步为什么保持它。

初始化：维护结构不变量 invariant
遍历/调整：每处理 1 个节点或元素，都只改变必要指针/索引
校验：操作后结构仍满足顺序、连通性或堆/树性质
复杂度：每个元素最多进入/离开结构 O(1) 或 O(log n) 次

九、一步步推演与边界

回答如何判断一个单链表是否为回文链表？时，最好额外走一遍小样例。先用 3～5 个元素演示正常操作，再故意加入空结构、单元素、重复值或极端位置，观察不变量是否仍成立。比如链表题要盯住前驱、当前、后继 3 个指针；树题要说明递归返回值代表什么；堆题要说明上浮/下沉什么时候停止；图题要说明 visited 或入度数组何时更新。

这种推演的价值在于把“我知道算法”变成“我能证明边界也不会错”。很多面试失分不是主流程不会，而是少了空节点、尾节点、重复边、环、K 越界这类边界。把这些点主动讲出来，既能减少代码 bug，也能让复杂度分析更可信。

边界类型	检查方式	容易出错的地方
空结构	输入为空或 root/head 为 null	直接访问属性导致异常
单元素	只有 1 个节点或元素	前驱/后继、左右子树判断错误
重复值	多个元素相等	比较条件写成 < 还是 <=
极端位置	头尾、最大最小、第一层最后一层	更新指针或索引越界

七、加强记忆

单链表判回文 O(1) 空间三步：快慢指针找中点 → 反转后半段 → 两头向中间逐个比值（因为单链表不能像数组那样反向夹，得先造出可反向走的后半段）。奇数长度时中间节点自动跳过。比完最好把后半段反转回去还原链表。图省事可拷进数组用双指针，O(n) 空间。

简化版

详细版