【LC 234】回文链表：把后半段翻过来，它应该跟前半段长得一模一样
适用读者：会写反转链表，但看到「O(1) 空间」四个字就忍不住想去开个数组的人
技术栈：Python 为主，附 Java 版
难度：简单（思路一句话就说完，但有三个细节一写就错）
收获：「找中点 + 反转后半段 + 逐对比较」这条套路，以及它为什么不用像重排链表那样断开
题目
给你一个单链表的头节点
head，请判断该链表是否为回文链表。
输入：head = [1,2,2,1]
输出：true
输入：head = [1,2]
输出：false
：你能否用
O(n) 时间复杂度和
O(1) 空间复杂度解决此题？
出处备注：美团测开等面试中出现频率很高的链表热身题，通常要求当场写出进阶解法。
链表节点的定义（后面所有代码都用它）：
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
一、先想清楚「回文」在链表上意味着什么
1.1 数组上的回文靠下标，链表没有下标
判断一个数组是不是回文，闭着眼都能写：
def is_palindrome(arr):
i, j = 0, len(arr) - 1
while i < j:
if arr[i] != arr[j]:
return False
i += 1
j -= 1
return True
它成立的前提是
arr[j] 能在
O(1) 时间里拿到。链表没有下标，
j 想从尾巴往回走，只能从头再走一遍 —— 那就
O(n²) 了。
所以链表上要玩回文，得先把"从后往前"这个动作，换成链表擅长的事。
1.2 核心洞察：后半段反转过来，应该跟前半段一模一样
把
1 → 2 → 2 → 1 从中间切开：
后半段
倒过来读是
1 → 2。跟前半段一模一样 —— 这就是回文。
前半段： 1 → 2
后半段反转后：1 → 2 ← 逐位相同
配对： ↑ ↑
1=1 2=2
再找个反例
1 → 2 → 3：
前半段： 1
后半段反转后：3 → 2 ← 第一位就对不上
一句话说完了，剩下的全是搬砖。
1.3 为什么这套能顺手把空间压到 O(1)
你可能会先想到：把值读进数组，再用双指针比。能过，但空间
O(n)，不是进阶答案。
而"反转后半段"这件事，
原地改指针就够了 —— 反转链表本来就是
O(1) 空间的。加上找中点用快慢指针也是
O(1)，全程只需要六根指针：
slow、
fast、
prev、
curr、
p1、
p2。
顺带一提：这题改的是链表结构（反转了后半段），题目没禁止。不像 LC 143 明着要求"必须实际改动节点"，234 只关心返回值，结构改了无所谓。
二、拆成三步：每步都是做过的题
这题的全部难度，就是看出它其实是三道做过的题拼起来的。
2.1 第 ① 步：slow 要停在后半段的开头
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
注意这里
两个指针都从 head 出发，跟重排链表那篇不一样。这个细节决定了
slow 停在哪：
- 长度 4：
slow 停在位置 2（第 3 个节点），前半段 位置0 → 位置1，后半段 位置2 → 位置3；
- 长度 5：
slow 停在位置 2（正中间那个），前半段 位置0 → 位置1，后半段 位置2 → 位置3 → 位置4。
也就是说：
中间节点归后半段。
对比一下 LC 143 的写法
slow, fast = head, head.next ——那里
slow 停在
前半段的最后一个，中间节点归前半段。两道题的取法
是反的，别串：
为什么 234 里中间节点归后半段无所谓？因为它
跟自己比必然相等，白比一次而已，不影响结论。反而放到后半段更省事：反转之后它自动落到后半段的末尾。
2.2 第 ② 步：反转后半段 —— 这里不需要断开
prev, curr = None, slow
while curr:
nxt = curr.next # 先记住
curr.next = prev # 再掉头
prev = curr # 后前移
curr = nxt
和 LC 206 逐字一样，只是起点从
head 换成了
slow。反转完，
prev 站在新段头（原来的尾节点）上。
这里是这题最有意思的一处：不用写 slow.next = None。
在 LC 143 里那一刀是命门 —— 少了它，合并时会把两个指针绕成环。但 234 只是
读值，不合并，所以：
- 前半段的尾巴（
位置1）的 next 依然指着中点 位置2；
- 反转时，中点
位置2 的 next 被置成了 None（它是反转的第一个节点）；
于是前半段从
head 走下去，走到中点就
自然停了。前半段这条通路恰好是我们要的长度 ——「尾巴还搭着」在这儿不是 bug，是正好借来用的。
反转后（长度 4）：
前半段链： 位置0 → 位置1 → 位置2 → ∅
↑ 中点的 next 被反转置空，走到这就停
后半段链： 位置3 → 位置2 → ∅
2.3 第 ③ 步：逐对比较，循环条件写 while p2
p1, p2 = head, prev
while p2:
if p1.val != p2.val:
return False
p1, p2 = p1.next, p2.next
return True
while p2，不能是 while p1。 因为偶数长度时，前半段那条链比反转后的后半段
多一个节点（前半段要走到中点才停，后半段到中点就停了）。
- 长度 4：前半段链有 3 个节点，后半段链只有 2 个。用
while p1 的话，p2 先走到 None，下一轮访问 p2.val 直接 NoneType 报错。
后半段永远是最短的那条，以它为准就对了。奇数长度时两边一样长，最后一对是中点跟自己比，必然相等。
三、动画：看着上下两列对齐
下面这个动画把
1 → 2 → 2 → 1 的全程拆成 9 步。留意三件事：
- 找中点：
fast 一次跨两格、slow 一次一格，fast 冲出链表时 slow 正好停在后半段的开头；
- 反转：后半段整体下移一行，箭头逐个掉头，最后整段"翻了个面"，从左到右读起来跟上行一样；
- 比较：上下两列一一配对齐，
p1 在上行往右走，p2 在下行往右走，每对之间竖着连一条线，相等打 ✓。
看完动画再回头看那句核心洞察 ——
后半段反转过来，跟前半段逐位相同，画面上就是上下两行长得一模一样。
四、完整代码
4.1 Python
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
if head is None or head.next is None:
return True
# ① 找中点：fast 一次两格、slow 一次一格
# fast 走完时，slow 正好停在后半段的开头（奇数长度时是正中间）
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# ② 反转后半段（LC 206 原样搬过来，起点换成 slow）
prev, curr = None, slow
while curr:
nxt = curr.next # 先记住
curr.next = prev # 再掉头
prev = curr # 后前移
curr = nxt
# ③ 逐对比较：以后半段为准，它更短
p1, p2 = head, prev
while p2:
if p1.val != p2.val:
return False
p1, p2 = p1.next, p2.next
return True
开头的
head.next is None 那句是防御性的：单节点直接返回其实算法也能算对（中点跟自己比），但显式写出来更稳，也省掉一轮反转。
4.2 完整推演表
以
[1,2,2,1] 为例（位置从 0 开始）：
再看个反例
[1,2,3]，看它怎么提前退出：
注意第 3 步就结束了 —— 后面那对根本不用比。这也是为什么回文判定要"一发现不等就返回"，而不是先全收集起来再比。
4.3 Java 版
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) return true;
// ① 找中点：slow 停在后半段的开头
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// ② 反转后半段
ListNode prev = null, curr = slow;
while (curr != null) {
ListNode nxt = curr.next; // 先记住
curr.next = prev; // 再掉头
prev = curr; // 后前移
curr = nxt;
}
// ③ 逐对比较：以后半段为准
ListNode p1 = head, p2 = prev;
while (p2 != null) {
if (p1.val != p2.val) return false;
p1 = p1.next;
p2 = p2.next;
}
return true;
}
}
五、边界情况
几个要记牢的：
- 空链表是回文。正着读反着读都是"什么都没有"。代码里
head is None 直接返回 True。
- 单节点是回文。算法上也是对的（中点跟自己比）。
- 奇数长度多比一次中点自己。写
while p2 就会遇到这个，结果是"必然相等"，不用特判。
- 比较对数 =
⌈L/2⌉，但有效判定只需要 ⌊L/2⌋ 对（中点那对是白送的）。
六、复杂度
- 时间
O(n)：找中点走 ⌊n/2⌋ 轮，反转走 ⌈n/2⌉ 个节点，比较走 ⌈n/2⌉ 对 —— 加起来不超过 1.5n 次指针访问。每个节点被访问的次数是常数，线性。
- 空间
O(1)：全程只用 slow、fast、prev、curr、p1、p2 六根指针，没有数组、没有栈、没有递归。
对照一下开数组的方案：时间也是
O(n)，但空间
O(n)。这题的
考点恰恰就是把那 O(n) 压成 O(1) —— 进阶要求写在题干里，不是随口一提。
七、常见坑
1. 比较循环写成 while p1 —— 直接 NoneType 报错。
偶数长度时前半段链比后半段链多一个节点，
p2 先走到
None。必须
while p2（
while p1 and p2 也对，但后半段最短，写
p2 最准，也最不容易改错）。
2. 中点取法跟 LC 143 串了。
两道题的
slow 落点是反的：143 停在前半段最后一个（中点归前半段），234 停在后半段第一个（中点归后半段）。
同一份代码里别混用两种起点：
slow=fast=head 配
后半段 = slow；
slow=head, fast=head.next 配
后半段 = slow.next。混了就会要么漏比一个、要么多比一个。
3. 多写了一句 slow.next = None。
在 234 里不必要，但也不算错 —— 前半段走到中点前一个就停了，比较对数少一次（中点不参与）。写了不会崩，只是
多余，而且会让"恢复链表"变麻烦（得先把断开的那条边接回去）。
4. 用递归比较。
def check(node): # 递归版：栈空间 O(n)
nonlocal front
if node is None: return True
if not check(node.next): return False
ok = front.val == node.val
front = front.next
return ok
很优雅，但递归栈是
O(n)，不满足进阶要求。写之前想清楚面试官问的是哪个。
5. 忘了空链表和单节点。
虽然这版算法本身能算对，但显式防御更稳 —— 尤其是那些在
fast.next.next 上做文章的写法，单节点时容易翻车。
6. 反转完不恢复，被追问时答不上来。
LC 234 不要求保持原结构，但面试官爱追一句"能恢复吗"。答案是
能，而且只要一行：因为全程没断开过，前半段的尾巴一直指着中点，把后半段再反转一次就自动接回去了。
reverse(prev) # 再反转一次，链表恢复原状
这个性质是 2.2 节"不用断开"顺手换来的，答出来很加分。
八、面试怎么答
开口 30 秒给思路（别一上来就写代码）：
回文就是"前半段"和"后半段倒过来"逐位相同。链表没法从后往前走，那就把后半段反转过来，再用两个指针从头比。分三步：快慢指针找中点、反转后半段、双指针逐位比。时间 O(n)，空间 O(1)。
然后主动把三个易错点交代掉 —— 这是区分"背过答案"和"真懂"的地方：
- 中点用
slow=fast=head，slow 落在后半段开头，中间节点归后半段；
- 不用断开 —— 反转时中点的
next 会被置空，前半段走到那儿自然终止；
- 比较循环写
while p2，因为偶数长度时前半段链更长。
追问应对：
- "能不用额外空间吗？" —— 已经是 O(1) 了，六根指针。
- "能恢复原链表吗？" —— 能，再反转一次后半段即可，因为全程没断开。
- "奇数长度中间那个怎么办？" —— 归后半段，反转后落到末尾，最后跟自己比一次，必然相等，不用特判。
- "还有别的 O(1) 做法吗？" —— 有，递归前后指针那套，但栈是 O(n)，严格说不算 O(1)。
结语
把这几篇串起来看，快慢指针这一家子的分工是这样的：
234 和 143 是同一副骨架（找中点 + 反转后半段），差别只在第三步：一个要
改拓扑（所以必须断开防环），一个只
读值（所以断不断都行，不断反而更省事）。
下次再遇到"从后往前"的链表题，先问自己一句：
后半段反转过来，是不是就变成了从前往后？ 如果是，这题就做完一半了。