空间搞定)
刷LeetCode的人基本绕不开链表这一关，而第234题“回文链表”又是链表题里被问得最勤的一道之一。它常驻热门100题，周赛里也经常作为更复杂题目的前置环节出现，平时面试手撕链表，出题人十有八九会拿它试水。题目本身一句话就能说清：判断一个链表是不是回文结构，也就是正着遍历和反着遍历得到的节点值序列是否一致。但越是看起来简单的题，坑越藏在细节里——快慢指针怎么找中点、奇偶长度怎么处理、反转链表会不会断链、比较到什么时候才算结束，随便一个环节没想透，代码就会在边界用例上翻车。这篇文章就围绕回文链表，把我实际刷题、调试、复盘的经验完整写出来，从思路选型到最优解原理，从可直接抄的代码到各种翻车实录，零基础的人能看懂，准备面试的人也能直接用。
1. 题目拆解：回文链表到底在考什么
1.1 回文的定义与链表带来的麻烦
回文（palindrome）的定义很简单：正着读和反着读都一样。数字 121 是回文，字符串 "abba" 是回文，链表1 -> 2 -> 2 -> 1同样也是回文。这个定义放到数组里几乎没有任何难度，因为数组天然支持随机访问，你可以直接用两个下标 left 和 right 从两端往中间走，比较对应的值就行。
但链表不行。单向链表只能从头节点开始沿 next 指针一路往后走，没有下标，不知道长度，更没法从尾部倒着向前走。你想比较第一个节点和最后一个节点，得先走到最后；比较第二个节点和倒数第二个节点，又得再走一遍。如果每比较一对节点都重新遍历一次，时间直接变成 O(n²)，在 LeetCode 上必超时。
所以这道题表面上考的是“是否理解回文”，实际上考的是“在不能随机访问链表的限制下，你如何把双向比较变成单向比较”。常见的手段无非三种：把链表的节点值复制到数组里再做双指针；用递归借助系统调用栈从后往前访问；或者修改链表本身的指针方向，让后半段能向前遍历。后面你会发现，这三种手段正好对应了这道题的三种解法，而最优解就是把它们结合起来用。
1.2 三条解法路线：选择与取舍
先说我第一次做题时的反应：遍历链表，把每个节点的值存进 ArrayList，然后用双指针从数组两端往中间比。这确实是最容易想到的解法，代码只有十几行，逻辑直白，时间复杂度 O(n)。但缺点是额外开辟了一个和链表等长的数组，空间复杂度也是 O(n)。如果面试官紧接着问一句“能不能用 O(1) 空间完成”，你就得当场换思路。
第二种解法是递归。设计一个类成员指针 front 指向链表头部，递归函数一路走到链表尾节点，然后在回溯的过程中把当前节点和 front 指向的节点逐个比较。这个写法的代码看起来很优雅，完全没有修改链表结构，但它的本质是借用了系统的函数调用栈，递归深度等于链表长度，空间复杂度同样是 O(n)。对于特别长的链表，还会面临栈溢出的风险。面试时可以作为“除了快慢指针法我还会递归法”的补充展示，但不适合作为最终答案。
第三种就是我后面要详细讲的快慢指针法：先用快慢指针找到链表的中间位置，然后把后半段链表原地反转，最后从头和后半段的头同时出发逐一比较节点值。时间 O(n)，空间 O(1)，是这道题最标准的“最优解”。之所以选择它而不选前两种，正是因为它的空间复杂度最低，同时这一套操作里包含了找中点、反转链表、双指针比较三个基本功，练熟这一题，等于把三道基础题一起复习了。三种方案放在一起对比会更直观：
| 解法 | 时间复杂度 | 空间复杂度 | 是否修改链表 | 适合场景 |
|---|---|---|---|---|
| 数组 + 双指针 | O(n) | O(n) | 否 | 快速验证思路、作为暴力解铺垫 |
| 递归 | O(n) | O(n) | 否 | 展示递归思想、面试补充方案 |
| 快慢指针 + 反转后半段 | O(n) | O(1) | 是（可恢复） | 最优解、面试主答案 |
2. 最优解原理：快慢指针加反转后半段
2.1 四步走：找中点、反转、比较、恢复
整个解法可以拆成四个阶段，拿1 -> 2 -> 3 -> 2 -> 1这个回文链表为例走一遍，你会很快明白每个步骤在干什么。
第一步，找中点。初始化 slow 和 fast 两个指针，都指向头节点。slow 每次走一步，fast 每次走两步。当 fast 走到链表末尾时，slow 恰好停在中间位置。对于1 -> 2 -> 3 -> 2 -> 1，slow 最终会停在值为 3 的节点上。
第二步，反转后半段。从 slow 指向的节点开始，把从中间到末尾的这一段链表反转过来。原始的后半段是3 -> 2 -> 1，反转之后变成1 -> 2 -> 3，这个新链表的头节点就是原来的尾节点，值也是 1。
第三步，双指针比较。p1 指向原链表的头节点（值为 1），p2 指向反转后的后半段头节点（值为 1）。两者同步向后移动，每移动一次比较一次p1.val == p2.val。在这个例子里，比较过程是 1 对 1、2 对 2、3 对 3，全部相等，所以是回文。
第四步，恢复链表。这一步在 LeetCode 上可以直接省略，因为判题系统只关心返回值，不关心链表结构是否被改变。但如果在面试里写代码，我会建议你在比较结束后把后半段再反转一次接回去，这个动作在面试官眼里是非常加分的工程意识。具体写法我在后面“原链表被破坏”那一节里给出。
偶数长度的回文链表同样适用。例如1 -> 2 -> 2 -> 1，快慢指针走完之后 slow 停在第二个 2 的位置，反转2 -> 1得到1 -> 2，比较时 1 对 1、2 对 2，结果正确。这里有个关键点，反转的起点是 slow 本身，而不是 slow.next。初学者很容易误以为要从中间节点的下一个节点开始反转，结果在奇数长度下丢掉中间节点，在偶数长度下丢掉半个右半段，导致判断错误。
2.2 奇偶长度与停止条件的边界分析
快慢指针的循环停止条件，传说中是个大坑。最标准也最安全的写法是：
while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }为什么必须同时判断 fast 和 fast.next？因为链表长度可能是奇数，也可能是偶数，两种情况下 fast 停下来的位置不一样。
奇数长度，比如1 -> 2 -> 3 -> 2 -> 1，fast 最终会停在最后一个节点（值为 1），这时 fast.next 为 null，循环因为fast.next != null不成立而退出。此时 slow 正好停在中间节点，值为 3。
偶数长度，比如1 -> 2 -> 2 -> 1，fast 走完最后一步之后会直接变成 null，循环因为fast != null不成立而退出。此时 slow 停在第二个 2 的位置，也就是中间偏右的那个节点。
这两种位置恰好都是我们想要的“后半段起点”。如果漏掉fast != null这个判断，偶数长度下会在循环里访问fast.next直接抛空指针；如果漏掉fast.next != null，奇数长度下同样会空指针。我见过有人把条件写成while (fast.next != null && fast.next.next != null)，这个变体在某些用例上能碰对结果，但 slow 的停靠位置变成了“前半段的最后一个节点”，导致反转范围变大，逻辑证明和恢复链表都变得很绕，不建议使用。
还有个细节值得单独说：比较阶段的循环条件，我坚持写while (p2 != null)，而不是while (p1 != null)或while (p1 != null && p2 != null)。原因很简单，反转后的后半段长度一定不会超过前半段，所以 p2 一定比 p1 先走到头。如果以 p1 为循环条件，在回文链表的奇数长度场景下，p2 已经变成 null 了，循环却还在继续，下一次访问 p2.val 就会空指针。直接用while (p2 != null)，既干净又安全。
3. 可直接复制的完整代码实现
3.1 Java版本：主流程与辅助函数
这里给出一个可以直接提交到 LeetCode 的 Java 版本，也是我日常刷题最常写的样式。提前对空链表和单节点链表做了特判，返回 true，因为空链表和只有一个节点的链表天然是回文。
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 p1 = head; ListNode p2 = secondHalf; boolean result = true; while (p2 != null) { if (p1.val != p2.val) { result = false; break; } p1 = p1.next; p2 = p2.next; } return result; } private ListNode reverse(ListNode head) { ListNode prev = null; ListNode cur = head; while (cur != null) { ListNode next = cur.next; cur.next = prev; prev = cur; cur = next; } return prev; } }reverse 方法里的三行操作顺序是铁律：先用 next 保存当前节点的下一个节点，再改变当前节点的 next 指针让它指向前一个节点，最后把 prev 和 cur 整体后移。顺序只要打乱，链表就会断在某个节点上，程序轻则返回错误结果，重则死循环。
3.2 Python版本：简洁写法与注意点
Python 写起来更短，逻辑完全一致。ListNode 定义里已经有了 val 和 next，直接操作即可。下面这份代码在 LeetCode 的 Python3 环境下可以直接跑通。
class Solution: def isPalindrome(self, head: Optional[ListNode]) -> bool: if not head or not head.next: return True # 找中点 slow, fast = head, head while fast and fast.next: slow = slow.next fast = fast.next.next # 反转后半段 second_half = self.reverse(slow) # 比较 p1, p2 = head, second_half while p2: if p1.val != p2.val: return False p1 = p1.next p2 = p2.next return True def reverse(self, head: Optional[ListNode]) -> Optional[ListNode]: prev, cur = None, head while cur: nxt = cur.next cur.next = prev prev = cur cur = nxt return prevPython 版本最容易犯的错有两个：一是while fast and fast.next里把顺序写成fast.next and fast，在 fast 为 None 时短路保护失效，直接报错；二是在 reverse 里先把cur.next改了再用cur = cur.next推进，结果 cur 永远在原处打转。每次都先保存nxt是唯一的解药。
3.3 复杂度推演：为什么空间是O(1)
这道题能在热门100题里站稳，很大程度是因为它把“最优解的空间复杂度是 O(1)”这件事体现得很典型。我们拆开算一遍：
- 找中点阶段，slow 和 fast 两个指针是常数空间，移动次数大约是 n/2，时间 O(n)。
- 反转后半段，只用了 prev、cur、next 三个临时指针，没有申请新链表，只是原地调整 next 方向，时间 O(n/2)，空间 O(1)。
- 比较阶段，p1 和 p2 是常数空间，比较次数不超过 n/2，时间 O(n/2)。
三部分串起来，整体时间复杂度 O(n)，额外空间 O(1)。这里的“额外空间”指的是与链表长度 n 无关的变量，而不是所有变量的总和。对比数组法的 O(n) 空间，快慢指针法的核心优势就是把空间从线性降到了常数，这也是面试中“空间优化”最常见的考察路径。
如果写递归解法，虽然代码看起来省去了显式的额外数据结构，但每递归一层，JVM 或 Python 解释器都要压一个栈帧，递归深度等于链表长度，空间同样是 O(n)。所以递归并不比数组法更省空间，只是把空间藏到了系统栈里。
4. 实操日志：我踩过的坑与排查过程
4.1 空指针来自哪里：快慢指针条件写错
我第一次独立写这题时，快慢指针的循环条件写成了while (fast.next != null && fast.next.next != null)，当时的想法是“让 fast 多判断一步，防止越界”。结果在偶数长度用例上，slow 停在的不是中间偏右节点，而是前半段的最后一个节点。那一次我在本地上跑了半天没发现问题，直到对比了两份代码的 slow 停靠位置才意识到，这种写法让慢指针少走了一步，后续反转和比较全都建立在错误起点上。
排查这种问题有个非常实用的土办法：在纸上画出长度为 4 和长度为 5 两条链表，手动模拟 fast 和 slow 每一步的移动，然后把代码里加一行System.out.println(slow.val)打印出来对比。绝大多数快慢指针问题，一画图就全清楚了。标准写法就是统一用while (fast != null && fast.next != null)，不要自己发明变体。
4.2 反转链表丢链的经典事故
反转段代码是另一个事故高发区。我见过最典型的一种错误写法是：
private ListNode reverse(ListNode head) { ListNode prev = null, cur = head; while (cur != null) { cur.next = prev; prev = cur; cur = cur.next; } return prev; }第三行cur = cur.next是错的，因为前面cur.next = prev已经把当前节点的 next 改成了 prev，再取cur.next得到的其实是前一个节点，cur 永远在原节点上原地打转。正确的做法必须先用一个临时变量保存原始后继节点。
这个坑的排查信号非常明显：程序要么死循环，要么最终返回的链表只有一两个节点。我自己的习惯是写完 reverse 立刻用一个1 -> 2 -> 3 -> null的手写链表单独测试一遍，反转结果必须是3 -> 2 -> 1 -> null，确认无误再接回主流程。把辅助函数单独验证，能省掉后面一大半组合调试的时间。
4.3 比较阶段的循环条件：p1还是p2
比较阶段写成while (p1 != null)是我见过的第二个高频错误。拿1 -> 2 -> 3 -> 2 -> 1举例，反转后的后半段是1 -> 2 -> 3，p2 长度为 3。p1 从头开始，第三轮比较时 p1 在中间节点 3，p2 也在中间节点 3；第四轮 p2 已经变成 null，但 p1 还在节点 2（对应原链表前半段的 2），如果循环条件看的是 p1，就会进入第四轮循环，访问p2.val，直接空指针异常。
解决办法很简单：比较的终点以后半段为准，也就是while (p2 != null)。长度关系上，后半段只会等于或短于前半段，所以 p2 为 null 时，即使 p1 后面还有节点，那些节点在奇数长度情况下本来就是多出来的左半部分，不需要再比较。这个细节记牢，回文链表的代码一遍过。
4.4 原链表被破坏：恢复的加分实现
不少同学刷题时会有一个疑问：我反转了后半段，原链表不是被改了吗？LeetCode 判题系统不检查链表结构，所以提交没问题。但真实面试中，把输入数据改坏通常是大忌。我建议在比较完之后把后半段再反转一次接回原链表。
下面这个版本在之前的代码基础上增加了恢复逻辑。找中点时顺手记录 midPrev 节点，比较结束后把 secondHalf 再反转一次，重新得到原始的后半段链表，然后让 midPrev 重新指向它，链表结构就和输入时完全一致了。
class Solution { public boolean isPalindrome(ListNode head) { if (head == null || head.next == null) return true; ListNode slow = head, fast = head; ListNode midPrev = null; while (fast != null && fast.next != null) { midPrev = slow; slow = slow.next; fast = fast.next.next; } ListNode secondHalf = reverse(slow); ListNode p1 = head, p2 = secondHalf; boolean result = true; while (p2 != null) { if (p1.val != p2.val) { result = false; break; } p1 = p1.next; p2 = p2.next; } // 恢复原链表：把后半段再反转一次，接回中点前一个节点 ListNode restored = reverse(secondHalf); if (midPrev != null) { midPrev.next = restored; } return result; } private ListNode reverse(ListNode head) { ListNode prev = null, cur = head; while (cur != null) { ListNode next = cur.next; cur.next = prev; prev = cur; cur = next; } return prev; } }注意这里的恢复逻辑对奇偶长度都适用。偶数长度时 midPrev 是前半段最后一个节点，restored 是原后半段的起点；奇数长度时 midPrev 是中间节点之前的一个节点，恢复后正好接回包含中间节点的后半段。这一版代码解决“结果正确但链表被改”的问题，面试时主动写出这种版本，通常会成为全场亮点。
4.5 三组用例走查：从输入到输出
为了让流程更直观，我整理了三个典型用例的完整走查，包括快慢指针最终位置、反转后的链表和比较结果。
| 输入链表 | slow 最终位置 | fast 最终位置 | 反转后的后半段 | 比较过程 | 结果 |
|---|---|---|---|---|---|
| 1 -> 2 -> 3 -> 2 -> 1 | 3（中间节点） | 1（末尾节点） | 1 -> 2 -> 3 | 1=1，2=2，3=3 | true |
| 1 -> 2 -> 2 -> 1 | 2（第二个2） | null | 1 -> 2 | 1=1，2=2 | true |
| 1 -> 2 -> 3 -> 4 | 3（中间偏右） | null | 4 -> 3 | 1≠4，立即终止 | false |
第三个用例尤其值得留意，比较到第一对节点值就不相等，直接返回 false，根本不需要走完整个链表。这也是双指针法比递归法更高效的一个隐含优势：它可以在发现第一个不匹配节点时立即退出，而不用等整个递归栈回溯结束。
5. 面试与刷题延伸：一道题带出一类题
5.1 面试官想看到的答题节奏
如果你在面试中遇到这题，面试官真正想看的大概率不是“你能不能默写出一个正确解法”，而是你面对一道基础题时会不会暴露思维漏洞。我建议的答题节奏是这样的：
先花二十秒说明思路，把回文判断的本质概括为“首尾对称比较”，并主动点出链表无法随机访问这个约束。然后给出数组法作为起点，一句话说明它的空间复杂度是 O(n)。接着自然过渡到优化：用快慢指针找到中点，把后半段反转，空间降到 O(1)，时间仍然是 O(n)。写代码之前，用语言描述一下奇数和偶数长度分别会有什么表现，让面试官看到你有边界意识。写完主流程后，主动提一句“这个实现会修改链表结构，如果需要保持原链表不变，可以在比较完成后把后半段反转回去”，然后快速补上恢复逻辑。
这个流程走下来，面试官对你的评价一般会落在“基础扎实、有优化意识、考虑问题全面”这一档，已经足够让这道题成为加分项而不是减分项。
5.2 高频关联题：一题吃透一簇
回文链表最妙的地方在于，它把几道基础题串成了一个整体。第一步找中点，几乎是第876题“链表的中间结点”的原题；第二步反转链表，对应第206题“反转链表”；而完整的“找中点 + 反转 + 合并/比较”流程，稍加改造就能解第143题“重排链表”。所以不必把每道题孤立地刷，拿下 234，等于顺手复习了至少三道相邻题目。
另外，如果从更宏观的刷题体系看，热门100题里这类“经典套路题”还有很多，比如爱吃香蕉的狒狒那种二分答案题，讲的同样是“在一个可行解空间里反复逼近最优解”的边界思维。它们和链表题不在一个维度，但共同点是：只要把底层套路吃透，题目形态怎么变都不慌。刷题的价值从来不是背题，而是把高频套路形成肌肉记忆。
5.3 从回文链表提炼的通用解题思维
这道题做完之后，值得沉淀下来的方法论有三条。
第一条，链表题的三板斧——快慢指针找中点、原地反转链表、双指针同步遍历。这三板斧可以自由组合，应对大量链表类题目。下次见到“重排链表”“旋转链表”“判断环形链表”时，你会发现满脑子都是它们的影子。
第二条，空间优化是有套路的。先写最直白的暴力解，再问一句“额外的空间能不能省掉”。数组法省不掉，因为随机访问依赖额外容器；递归法的空间藏在系统栈里，表面上省了实际没省；快慢指针法通过改变链表自身的指针方向，把空间真正降到了 O(1)。这种“从显式容器到隐式容器，再到不依赖容器”的优化路径，比其他任何结论都值得记住。
第三条，边界条件靠画图驱动。写循环条件之前，先画出长度为 4 和长度为 5 的两条链表，手动标出 slow 和 fast 每一步停在哪。只要这一步做了，快慢指针的终止条件、反转起点、比较终止条件三个细节全部一目了然。很多看似复杂的链表 bug，本质上都是动手画图就能避免的。
我个人刷这道题的完整经历是：第一版数组法五分钟写完通过，当时觉得这题不过如此；后来面试被追问空间复杂度，回来重写快慢指针法，光是循环条件就调了半小时。从那以后，我遇到任何链表题都会先画图再写码，这个习惯让我在后续几十道链表题里几乎没再因为边界问题翻过车。回文链表最值钱的地方不在于题目本身有多难，而在于它把链表操作里最核心的几块积木全部拼了一遍。如果你能把找中点、反转、恢复写得像呼吸一样自然，后面再去做重排链表、判断回文数的链表版本、设计链表这类题目，都会明显轻松不少。
