先说我自己的一个切身体会。以前刷到回文链表这道题时，第一反应是：数组回文我会啊，左右两个指针一夹，逐个比较就完事了。可链表这东西只能顺着 next 往后走，想回头就得想别的办法。LeetCode 第 234 题回文链表，正好把这个问题逼到墙角：栈辅助法可以很直观地借后进先出把后半段倒过来；双指针法则可以用“快慢指针找中点 + 反转后半链表 + 同步比较”把额外空间压到 O(1)。这道题适合所有准备技术面试、或者想把链表基本功打扎实的人，它几乎串起了链表题里最高频的三块积木：找中点、反转、双指针同步走。

1. 题目拆解：回文链表难在哪，以及最朴素的实现

1.1 单链表的单向性，是所有麻烦的根源

回文的定义是正着读和倒着读一样。数组能直接通过下标访问任意位置，首尾比较非常自然，一个 while 循环就能搞定。单链表的节点只有 val 和 next，没有 prev，你拿到最后一个节点时，没法凭它回到上一个节点。这就像一条单向的胡同，你走到尽头之后就只能原路跑回入口，而链表连“原路”这个能力都没有。所以问题的本质不是比大小，而是如何在单向结构里模拟“从尾部向头部走”。

实际面试里，很多同学能立刻写出数组法，因为第一个念头就是“遍历一遍把值记下来”。这个思路完全正确，只是后续需要追问“能不能不借助容器”。能意识到链表和数组的差异，本身就说明你理解了数据结构的基本特性。这道题不是什么偏题怪题，它就是把你学过的链表操作串起来，看看你能不能在实际场景里用出来。

1.2 题目约定：空链表、单节点都算回文

LeetCode 234 的输入是单链表头节点 head，输出是布尔值。题目明确空链表也返回 true，单节点当然也是 true。很多实现里空链表会直接漏掉，因为后面找中点时 fast.next 会报空指针错误，所以第一行永远先写空判断和单节点判断。

面试时我一般还会和面试官确认两件事：第一，允不允许修改输入链表；第二，对额外空间的限制是什么。这两个问题不是无意义的寒暄，它们会直接决定你选哪种方案。如果没有空间限制，最省事的实现是数组法；如果面试官明确说“能不能做到 O(1) 空间”，那答案必然是快慢指针加反转。这种确认过程本身也是面试考察的一部分，它能看出你写代码之前有没有建模和沟通的习惯。

提示：很多人的第一反应是“这题不就是遍历一遍存进数组再比较吗”，这个方向没有问题，但它只是起点，不是终点。

1.3 数组复制法：正确性优先的 baseline

无论最终用哪种方法，我建议先把数组法写出来，或者至少在纸上推演一遍。思路很简单：第一次遍历把链表节点的 val 依次放进一个列表，第二次用左右两个下标从两端往中间比较。代码如下：

def isPalindrome(head): vals = [] cur = head while cur: vals.append(cur.val) cur = cur.next left, right = 0, len(vals) - 1 while left < right: if vals[left] != vals[right]: return False left += 1 right -= 1 return True

这段代码时间是 O(n)，空间也是 O(n)。它的价值不在于省内存，而在于逻辑最为直观，适合拿来当正确性基准。后面写双指针法时，如果某个用例结果不对，我会拿数组法的输出来对拍，立刻能定位是反转出了问题，还是比较循环的边界出了问题。

从这题开始，我养成了一个习惯：任何链表题的实现，先列测试用例，再写代码。空链表、单节点、偶数回文、奇数回文、偶数非回文，这五个用例能覆盖大部分边界。先保证最笨的方案正确，再追求好方案，是刷题效率最高的路径，没有之一。

2. 栈辅助法：不擅长随机访问时，就借一个后进先出的容器

2.1 栈为什么天然匹配回文判断

回文的本质是前半段的正序等于后半段的逆序。链表没法逆序遍历，但栈可以。你只需要把前半段依次压进栈，再依次弹出，弹出的顺序就是前半段的逆序。这相当于给链表补上了一个“回看”的机制。

你可以把栈想象成一叠盘子：你一张张把盘子从下往上放，最后放上去的在最上面，取的时候却最先被取出来。这种特性正好能把顺序翻过来。数组法和栈辅助法在时间、空间复杂度上完全一样，都是 O(n)，但栈的代码思路更呼应链表结构，也更接近后续双指针法的雏形。

所以我在面试中经常把它作为“数组法之后的第二个方案”抛出来，面试官也容易顺着这个话题引导你优化。你先展示自己会栈，再说栈的空间不够优，最后引出反转链表，整套表达会非常自然。

2.2 全量入栈：最好写的版本

最简单的写法是把整条链表所有节点都压进栈，然后再从头遍历一次链表，每次弹出一个栈顶元素比较。如果中途遇到不相等，直接返回 false。遍历结束后返回 true。

def isPalindrome(head): stack = [] cur = head while cur: stack.append(cur.val) cur = cur.next while head: if head.val != stack.pop(): return False head = head.next return True

这个版本思路极简，缺点是做了很多无用功：后半段压进栈之后，前半段也要压进栈，然后又把后半段和整个链表再比较一遍。空间仍然是 O(n)，但实际浪费明显。唯一的优点是代码不容易出错，适合在时间紧张的时候先交一版能跑通的。

不过面试里最好不要止步于此，因为接下来那个“只入栈一半”的优化很自然会浮现出来。你只要想到“比较只需要后半段的反序”，就应该意识到前半段其实不用压栈。这个优化会引出快慢指针，而快慢指针正是最优解的前置知识。

2.3 优化：只入栈前半段

想省一半空间，可以先用快慢指针找到链表中点，然后把前半段入栈，再从后半段开始和栈顶依次比较。对奇数长度的情况，需要把中间节点跳过去，因为中间节点和它自己比较没有意义。

def isPalindrome_half_stack(head): if not head or not head.next: return True slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next stack = [] cur = head while cur != slow: stack.append(cur.val) cur = cur.next # 如果 fast 不为空，说明链表长度为奇数，跳过中间节点 if fast: slow = slow.next while slow: if slow.val != stack.pop(): return False slow = slow.next return True

这段代码有个细节：快慢指针结束时，如果 fast 是 None，链表长度是偶数；如果 fast 非空，长度是奇数。你可以用 [1,2,2,1] 和 [1,2,3,2,1] 分别跑一遍，观察 slow 最后停在哪。

我建议你手动推演一次这个过程，而不是直接背代码。因为在纸上画出 slow 和 fast 每一步的位置之后，你会真正理解“为什么奇数长度要跳过中间节点”，而不是凭感觉写 if。经过这样的手动推演，你对快慢指针的理解会扎实很多。栈方案尽管已经优化，空间复杂度依旧是 O(n)，因为大 O 只关心量级，O(n/2) 就是 O(n)。如果面试官要求空间降低到 O(1)，就得进入下一节的方法。

3. 双指针法：一次遍历找中点，把后半段原地反转

3.1 三个动作，拆开看全是基本功

这是面试官最希望听到的解法。它分三步：第一步，快慢指针找中点，慢指针每次走一步，快指针每次走两步，快指针到末尾时，慢指针正好在链表中间；第二步，反转后半段链表，从中间节点之后开始，用迭代方式原地反转，不申请额外空间；第三步，两个指针从两端同步走，前半段链表头作为左指针，反转后的后半段链表头作为右指针，逐个比较 val。

很多人一听到“反转链表”就想绕开，但其实这一步正是回文判断的关键。后半段原本是“从中间到尾部的顺序”，反转之后变成了“从尾部到中部的顺序”。现在左指针从头往后走，右指针从尾往前走，两者方向就正好对上了。相当于你把一根绳子从中间拎起来，再把后半截折回到起点，让两股绳子对齐比较。

这里我还想强调一下，为什么不是反转前半段。从原理上说反转哪一半都可以，但反转后半段有一个额外好处：慢指针找中点时，前半段链表不需要额外记录前驱信息，你只需要记住一个 middle 位置，然后从 middle.next 开始反转。代码结构最干净，恢复时也最方便。

3.2 奇偶长度到底怎么处理

这里是最容易写错的地方。以偶数链表 [1,2,2,1] 为例，快慢指针走完时，slow 停在第二个 2，反转从 slow.next（也就是第二个 1）开始，得到 [1,2]（注意方向是原链表的最后一个 1 成为头）。左指针指向原链表头 1，右指针指向反转后的头 1，比较过程完全对称。

奇数链表 [1,2,3,2,1] 走完时，slow 停在 3。反转从 slow.next 开始，即 [2,1] 反转为 [1,2]。比较时右指针会先走完，此时左指针还剩中间节点 3 没有比较。但因为中间节点在回文里一定等于它自己，所以比较循环只需要关注右指针是否为空，也就是 while right，不需要管左指针。

这背后的原因很简单：反转的是“中点之后”的那一段，右半段长度最多比左半段少 1。因此以短的一侧作为循环条件，天然安全。如果你写 while left and right，在奇数链表里会多比较一次中间节点，虽然结果也对，但逻辑不够干净，面试时也容易让面试官觉得你对边界理解不透。

3.3 O(1) 空间完整实现，并考虑恢复原链表

迭代反转不会占用调用栈，所以空间能做到 O(1)。下面这段代码把找中点、反转、比较、恢复原链表全部写在一起：

def reverseList(head): prev = None cur = head while cur: nxt = cur.next cur.next = prev prev = cur cur = nxt return prev def isPalindrome(head): if not head or not head.next: return True # 1. 快慢指针找中点 slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next # 2. 反转后半段 second = reverseList(slow.next) # 3. 同步比较 left, right = head, second result = True while right: if left.val != right.val: result = False break left = left.next right = right.next # 4. 恢复链表（可选，但面试加分） slow.next = reverseList(second) return result

注意代码里第 4 步是把反转后的后半段再反转一次，并重新接回 slow.next。很多人以为不恢复也没事，但如果面试官让你连续执行两次判断，或者后续还有别的代码依赖原链表结构，链表被改坏就会出问题。养成“用完复原”的习惯，是链表题里非常拉好感的一点。当然，如果函数只负责返回布尔值，并且题目没禁止修改，不恢复也说得过去。我习惯先问清楚，再决定要不要恢复。

这段代码还有一个值得注意的点：比较过程中如果发现不相等，我并没有立刻 return False，而是用一个 result 变量记录结果，然后跳出循环，先执行恢复，最后才返回 result。这个细节很关键，它保证了无论比较是否成功，链表都能恢复原状。

3.4 常见误解：反转会不会把链表弄丢

有同学担心反转后半段后，前半段也跟着乱了。其实不会。反转从 slow.next 开始，slow 之前的节点指针完全没动。反转过程中确实会修改后半段节点的 next 方向，但 head 到 slow 这一段仍然保持原样。比较时左指针沿着原来的前半段走，右指针沿着反转后的后半段走，两条线路互不干扰。

但这里有个隐藏前提：你必须保证 slow 本身不被修改。如果你写成 reverseList(slow)，把中间节点也卷进反转，那么链表的连接关系会变得很难恢复，代码也容易翻车。所以“从 slow.next 开始反转”不是随便选的，它是让前半段结构保持完整的关键。

我记得第一次写这个解法时，就直接对 slow 做了反转，结果后半段和前半段出现了交叉指向，调试了很久才意识到问题。后来我把“找中点”和“反转后半段”两个动作彻底分开理解，再也不犯这个错了。

4. 递归回溯法：语法上最优雅，代价也最隐蔽

4.1 递归怎么做到“从尾部往前走”

如果说栈是显式地用容器存数据，那么递归就是隐式地用系统调用栈完成同样的事。递归函数会先一路调用到链表的最后一个节点，然后在每一层回溯时往回处理。回溯的顺序正好是链表的逆序。

你可以把递归理解成传话游戏：第一个人只管把问题传给下一个人，等最后一个人拿到答案后，再一层一层往回传。传到最外层的时候，你已经“看过”了链表尾部。所以递归天然适合需要从尾到头访问链表的场景。

很多链表题都有这种“递归版”。比如反转链表可以用递归，回文判断也可以用递归。理解了这种模式后，你会逐渐发现，递归本质上是把“后进先出”的逻辑藏进了函数调用里。它和你显式写一个栈在思路上是等价的，只是表现形态完全不同。

4.2 代码实现：一个外部指针加一个递归函数

实现思路是：维护一个 front 指针，初始指向链表头。递归函数每次先递归到 next，等回溯时比较当前节点和 front 的 val，然后让 front 向后移动一格。

class Solution: def isPalindrome(self, head): self.front = head return self._check(head) def _check(self, node): if node is None: return True if not self._check(node.next): return False if self.front.val != node.val: return False self.front = self.front.next return True

这段代码读起来很清爽，但有一个容易踩的坑：front 必须是对象成员变量，或者使用列表、可变对象来包装，不能简单地在普通局部变量之间传递。因为每次递归回溯时都需要“上一次访问过的 front 位置”，如果 front 作为参数传下去，回溯时它已经停留在最深层的位置，无法自然恢复。

从执行流程看，递归会先沿着链表一直走到 tail 的下一个空节点，然后开始返回。第一次回溯时，node 是 tail，front 是 head，所以比较的是 head 和 tail。第二次回溯时，node 是倒数第二个节点，front 已经移动到 head.next，所以比较的是第二对。整个过程就像左右指针在链表上从两端相向而行，只是右指针的移动靠的是递归回溯。

4.3 为什么我不建议把它作为主解

递归版本的时间复杂度是 O(n)，空间复杂度严格说是 O(n)，因为递归深度等于链表长度。而且这个“空间”是系统栈，不是显式的容器，往往更容易被忽视。Python 默认递归深度大约 1000，一旦链表长度上千，程序直接报 RecursionError。即使语言允许很深递归，也会比堆内存更快耗尽。

所以在面试里，我会把递归法作为“我还能想到的另一种思路”来展示，而不是主打方案。它最大的价值是证明你对递归和调用栈有理解，而不是真的指望用它解决超长链表。主动提一句“不过递归有栈深度风险，所以我会优先考虑迭代方案”，这句话能体现你对工程边界的敏感，面试官往往很吃这一套。

如果你想把递归法练熟，建议找几道类似的题一起做：反转链表、两两交换链表中的节点、删除排序链表中的重复元素。这几道题都能用递归写，写多了你就会发现，递归回溯的方向感是共通的，练一次顶好几次。

5. 面试现场怎么打：方案取舍、复杂度博弈与代码边界

5.1 从最朴素到最优的表达顺序

我见过两类人：一类上来就背出 O(1) 空间的最终代码，另一类只会写数组法。前者容易让面试官怀疑你是背题，后者又暴露了链表基本功不足。最稳的做法是先给一个最直观的解法，再说明它的短板，然后逐步优化。

可以这样组织语言：第一步说“数组法或栈辅助法，O(n) 额外空间，优点是正确性一眼可见”；第二步说“如果要 O(1) 空间，关键在于让后半段逆序可访问，而链表反转恰好能做到”；第三步写快慢指针找中点加反转后半段；第四步补充边界条件和恢复链表。这套表达顺序其实就是在复现你自己思考问题的过程。

面试官要的不是一个最终答案，而是你面对一个问题时的建模能力。能把“为什么想到反转”讲清楚，比默写代码值钱得多。我自己的经验是，讲思路的时候尽量配合手势或者在白板上画图，边说边画“找中点、折返、对齐”这三个动作，对方很快就能跟上你的节奏。

5.2 复杂度对比与选型逻辑

用一张表把几种方案放在一起看：

注意表格里的“是否修改链表”一栏。快慢指针+反转如果不恢复，输入链表确实被改了。题目通常只看返回值，但工程上“函数不要有意外副作用”是良好习惯，所以我建议恢复。这也是为什么我在双指针法里专门加了恢复步骤，它不改变复杂度，但明显提升代码质量。

5.3 面试官可能会追问的三个方向

第一个追问：如果链表很长，甚至不能一次性全部读入内存，怎么办？这时通常用快慢指针流式比较，或者结合外部存储的离线思路，核心仍然是“找中点+分段”。这个追问考察的是你有没有考虑过数据规模超过内存的情况。

第二个追问：能不能用递归？可以，但要解释栈深度风险。如果没有提前说，面试官可能会认为你对运行时限制不敏感。你可以顺势说“递归在概念上等价于栈辅助法，但系统栈更容易爆，所以工程上我会选迭代”。

第三个追问：如果链表是双向链表，题目是不是更简单？是的，双向链表可以从尾节点往前走，理论上不需要反转。这个追问其实在考查你是否理解数据结构的差异如何影响算法设计。你不需要真的写双向链表版本，只要说“有 prev 指针就能从后向前走，回文判断会变成纯双指针移动”，就足以证明你理解了本质。

6. 手写实现时踩过的坑与我的调试习惯

6.1 三个高频 bug：初始化、断链、循环条件

先看快慢指针初始化。如果写成 slow = fast = head，循环条件用 while fast and fast.next，得到的中点位置是我上面用的这种。如果从 head.next 开始，边界就完全不同，别两种写法混着记。我见过不少同学在两种写法之间来回切换，最后在奇数长度链表上翻车。

再看反转链表。新手最常见的问题是忘记保存 nxt，导致 cur.next 指向前一个节点后，原来的下一个节点找不到了。我写反转前会习惯性先写一行 nxt = cur.next，再动 cur.next，这个顺序不能反。你可以把链表反转想象成换座位：你先把旁边人的位置记住，才能让现在的人站起来，否则一转身就找不到方向了。

最后是比较循环条件。有人写 while left and right，在奇数链表里会额外比较中间节点，虽然结果也对，但逻辑不干净。我建议写 while right，右半段比较完就结束，语义更准确。这个细节不会影响正确性，但能体现出你对回文定义的理解。

6.2 我自己的测试用例清单

手写链表题最怕边界，我的固定测试集基本是这样的：

• 空链表：[]，返回 true
• 单节点：[1]，返回 true
• 偶数回文：[1,2,2,1]，返回 true
• 奇数回文：[1,2,3,2,1]，返回 true
• 偶数非回文：[1,2,3,4]，返回 false
• 前半后半同值但长度不同的：[1,2,2] 这种，重点看循环条件会不会越界

实际刷题时我还会把一个特殊用例加进去：[1,2,1,1] 或者 [1,1,2,1]，这类结构很容易让只写对了一半的代码露馅。你可以在本地把链表构造函数写好，然后一次性跑完整个测试集，比在 OJ 上反复提交试错快得多。

调试链表有个笨但有效的办法：在纸上画出每一步。快慢指针走一步画一步，反转时给每个节点标上前驱、当前、后继三种状态。很多边界问题，画完图一眼就能看出来。代码里也可以临时加 print 打每个节点地址，比对着空屏猜要快得多。

6.3 从这道题延伸出去的链表套路

主流的链表题基本都是几个固定套路排列组合：快慢指针找中点、反转链表、合并有序链表、删除节点。回文链表是“找中点+反转+双指针比较”的经典组合。如果你把这三个动作拆开练熟，之后再遇到重排链表、旋转链表这类题，上手速度会快很多。

我的体会是，不要急着背整段答案，而是把每个动作单独练到肌肉记忆。比如反转链表今天写三遍，明天再写三遍，直到不用想就能写对。考试的时候真正卡住人的，往往不是“没想到反转”，而是反转代码里 next 断链的瞬间。