第一次刷到 LeetCode 234 回文链表这道题时我以为自己看走眼了判断一个链表是不是回文不就等于“正着读一遍、倒着读一遍都一样”嘛。于是第一版代码理所当然地把所有节点值装进数组再用 Python 的切片反转一比较测试用例一次通过我还挺得意。直到看到题目描述里的进阶要求——O(n) 时间、O(1) 空间才发现这条路根本不算数。回文链表真正的考点从来不是“怎么判断回文”而是“链表这种只能从前往后走的数据结构怎么实现从后往前比”。这篇文章把这道题的完整思考链路、常见解法的取舍、边界条件和面试时容易被追问的点都捋了一遍适合准备算法面试、或者链表反转/快慢指针掌握得还不太牢靠的人参考。1. “回文链表”到底在考什么链表的顺序访问限制1.1 回文定义很简单难点在链表结构本身回文说白了就是对称。1 - 2 - 2 - 1是回文1 - 2 - 3 - 2 - 1也是回文。如果输入是数组这个问题几乎没有难度左右各放一个指针一个往右走、一个往左走碰到不相等就直接返回 false。但链表不一样。单链表每个节点只有next指针从头节点出发你只能一直往后走没有办法从尾节点往前回退。也就是说“从两端向中间靠拢”这种数组时代的直觉在链表上根本使不出来。想让一个只能往后走的结构完成“从后往前”的遍历本质上只有三条路用数组、栈之类的额外容器把节点值缓存下来再间接实现倒序访问。用递归让系统调用栈替你做“倒序遍历”。修改链表结构把后半段或前半段原地反转把“从后往前”变成“从前往后”。LeetCode 234 的进阶要求限定了 O(1) 空间实际上就是在逼你走第三条路。这题换句话说就是找链表的中点把后半段反个方向然后双指针比较。这三个操作单独拎出来都不算难但组合在一起指针在什么位置、奇偶长度怎么处理、比较到什么时候停任何一个环节出错都会让代码看起来“差不多但又不对”。1.2 题目难度不高但组合考点很密这道题在题库里被标成简单题但实际面试中出现的频率不低因为它的信息密度很高。一个候选人能不能在十分钟内给出 O(1) 空间的解法往往能反映出两件事是否熟悉快慢指针找中点的写法是否真的理解链表反转的指针操作而不是背模板。而且这题天然适合层层追问。你给出数组法面试官会问“能不能优化空间”你给出反转解法面试官会问“如果函数结束之后还要继续使用这个链表怎么办”你提到递归面试官会问“递归的空间复杂度是多少”。所以它表面上是一道“会就是会不会就是不会”的题实际上是一张可以不断深挖的考卷。2. 数组法和栈法为什么只能算热身2.1 数组法三行代码过测试但没碰到题眼先看最直接的写法class Solution: def isPalindrome(self, head: ListNode) - bool: vals [] while head: vals.append(head.val) head head.next return vals vals[::-1]这段代码逻辑完全正确vals[::-1]是 Python 里很方便的列表反转方式列表比较会逐元素判断。时间复杂度 O(n)空间复杂度 O(n)。它能通过所有测试用例但问题在于它把链表先改写成数组然后用数组的方法解题链表这个数据结构本身的特性完全没有参与到解题过程里。面试时如果只给出这个版本对方很难判断你的链表基本功到底怎么样。我有一次模拟面试时故意先交这个答案对面直接追问了一句“如果链表有 1 亿个节点你还敢这么写吗”——那一刻就暴露了问题。说句公道话数组法不是没用。它适合在分析题目时快速验证自己的理解也适合作为暴力和最优解之间的对比起点。但如果你把它当最终答案那就等于主动放弃了这道题最重要的训练价值。2.2 栈法用“先进后出”模拟倒序空间减半但仍然是 O(n)栈的思路也很自然链表只能往后走栈却可以“后进先出”那我把前一半节点压进栈再从中间节点开始往后走依次弹栈比较不就从后往前遍历了吗代码如下class Solution: def isPalindrome(self, head: ListNode) - bool: slow fast head while fast and fast.next: fast fast.next.next slow slow.next stack [] cur head while cur ! slow: stack.append(cur) cur cur.next if fast: slow slow.next while slow: if stack.pop().val ! slow.val: return False slow slow.next return True这个版本比数组法稍微进了一步因为它开始使用快慢指针定位中点只压入前半段节点。但空间复杂度依然是 O(n/2)在大 O 表示法里还是 O(n)并没有满足进阶要求。而且代码里多出来的if fast处理奇数长度逻辑恰恰是很多人写错的地方。栈法的价值在于帮你想明白一件事“倒序访问”到底需要付出什么代价。数组付出了额外空间栈也付出了额外空间递归付出的是调用栈空间只有原地反转不需要这些。带着这个视角再去理解快慢指针反转就不会觉得它只是某个花哨技巧而是自然推导出的结果。3. 快慢指针找中点 反转后半链表最优解完整拆解3.1 快慢指针为什么能找到中点先用最朴素的语言描述两个指针同时从头部出发快指针一次走两步慢指针一次走一步。当快指针走到链表末尾时慢指针刚好走了快指针一半的路程也就是链表的中点附近。这就像两个人跑步速度差一倍同时起跑快的到终点时慢的一定在赛道中间。代码写出来只有三行slow fast head while fast and fast.next: slow slow.next fast fast.next.next循环结束时slow停在哪里取决于链表长度长度为奇数1 - 2 - 3 - 2 - 1时slow停在正中间节点3长度为偶数1 - 2 - 2 - 1时slow停在两个中间节点中靠右的那个。这个差异很重要。后面反转哪一段、比较到什么时候停都由slow的位置决定。3.2 反转链表的标准步骤三个指针一个都不能少反转链表的迭代写法是很多人的基础操作但写顺手之后反而容易忽略细节def reverse(head): prev None cur head while cur: nxt cur.next cur.next prev prev cur cur nxt return prev注意nxt cur.next这一行必须放在cur.next prev之前。因为一旦把当前节点的next指向前一个节点原来后面的节点就找不到了必须先保存下来。三个指针prev、cur、nxt分别承担“已反转部分的头”、“当前待反转节点”、“后面还没处理的节点”三种角色缺一个都会断链。3.3 完整实现三段逻辑拼在一起把找中点、反转后半段、双指针比较拼起来就得到这道题的核心解法class Solution: def isPalindrome(self, head: ListNode) - bool: 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. 反转以 slow 为头的后半段 prev None cur slow while cur: nxt cur.next cur.next prev prev cur cur nxt # 3. 双指针比较 left, right head, prev while right: if left.val ! right.val: return False left left.next right right.next return True拿1 - 2 - 3 - 2 - 1走一遍快慢指针结束后slow指向中间的3反转后半段3 - 2 - 1得到1 - 2 - 3left从原链表头出发right从反转后的头出发。第一次比较1 1第二次2 2第三次3 3然后right变成None循环结束返回True。时间上找中点走一遍、反转走一遍、比较走一遍总共约 3 次遍历O(n)。空间上只用了几个指针变量O(1)。3.4 奇偶长度处理为什么比较条件是while right而不是while left这是最容易写错的地方。奇数长度时slow是正中间节点反转后半段时把中间节点也包含了进去所以right所代表的“后半段”比“前半段”多一个节点。但比较过程中最后一对比较正好是“中间节点 vs 中间节点”也就是自己比自己不影响结果。所以不管奇数还是偶数right都不会比left长用while right做终止条件最安全。如果你非要用while left遇到非回文链表时left可能已经走到None而right还有剩余节点这时候代码会继续尝试访问left.val导致空指针异常。所以建议统一写成while right这是用最少的边界分支处理奇偶差异的标准做法。4. 递归解法通得过评测但别把它当成标准答案4.1 递归如何实现“从后往前”递归的核心思路是函数自己调用自己时最深层的那次调用会先接触到尾节点然后逐层返回。既然返回顺序天然就是“从尾到头”那我可以让一个外部指针front从头节点开始在递归返回的过程中和当前节点一一比较。class Solution: def isPalindrome(self, head: ListNode) - bool: self.front head def dfs(node): if not node: return True if not dfs(node.next): return False if self.front.val ! node.val: return False self.front self.front.next return True return dfs(head)递归到最深层node None时返回True然后倒数第一层拿到的是尾节点此时front指向头节点两个端点先比较比较成功后才把front往后移一个节点。就这样一个从尾往回走一个从头往后走在中点附近完成全部比较。这个写法很优雅代码也短甚至不需要自己手动找中点和反转链表。但它有一个致命问题递归深度等于链表长度。Python 默认递归深度在 1000 左右只要链表长度稍微大一点直接RecursionError。就算换成支持深递归的语言调用栈占用的空间依然是 O(n)不符合题目进阶要求的 O(1) 空间。4.2 我的建议可以展示思路但别当压轴答案面试时如果先抛递归版面试官很可能会顺着问“递归的空间复杂度是多少”“能不能不用额外空间实现”。这时候你再切换回快慢指针反转的版本会让整场对话显得很有层次先证明你理解“用调用栈模拟倒序”再证明你能写出真正符合要求的原地算法。反过来如果一上来就把递归版当作最终答案对面只会觉得你背了一个取巧的模板并没有理解这道题想考察的链表操作。所以我的结论是递归版适合作为思路铺垫不适合作为最终交付。它能帮你建立“倒序访问需要额外机制”的直觉但工程场景里没人会用一个可能栈溢出的算法去判断链表回文。5. 进阶变体边找中点边反转前半段省一轮遍历5.1 为什么可以一边走一边反转第三章的方案需要找中点和反转两个独立阶段运行时大概要遍历三次链表。能不能省掉一次可以思路是在快慢指针移动的过程中顺手把慢指针走过的节点反转掉。慢指针从前往后走的过程中它经过的每一个节点都已经“看过”了后面不会再按原顺序访问这些节点因为后面比较时前半段要逆序访问。那不如直接把前半段原地反转等快指针走到末尾时前半段已经是一个完整的逆序链表后半段还是原来的顺序。这样找中点和反转就在同一次遍历里完成了。5.2 代码实现与奇数长度陷阱class Solution: def isPalindrome(self, head: ListNode) - bool: if not head or not head.next: return True slow fast head prev None while fast and fast.next: fast fast.next.next nxt slow.next slow.next prev prev slow slow nxt if fast: slow slow.next left, right prev, slow while right: if left.val ! right.val: return False left left.next right right.next return True这里最关键的是if fast: slow slow.next。当链表长度为奇数时快指针最后停在最后一个节点上fast不为空此时slow正好停在正中间节点。这个中间节点在前半段反转时没有被包含进去后半段比较时可以跳过它所以slow slow.next把它让掉。如果链表长度是偶数快指针最后会停在None这时slow正好指向后半段的起始节点不需要额外处理。这段代码我每次默写时都要格外小心因为if fast这个判断太容易漏。漏掉的后果就是奇数长度的链表会把中间节点也拿去比较常见的情况是1 - 2 - 1也能通过但1 - 2 - 3 - 2 - 1这种长度更长的奇数回文会出错或者出现空指针。5.3 两个方案怎么选面试建议用第三章版本两版对比在最直观的维度上有这些差异对比项快慢指针 反转后半段边找中点边反转前半段代码可读性逻辑分段清晰容易解释指针变换集中容易绕晕额外遍历次数约 3 次约 1.5 次奇数长度处理天然兼容不需要额外分支必须判断if fast并跳过中点恢复原链表只需再反转一次后半段恢复过程复杂适合场景面试主推方案展示优化意识时使用我的经验是面试讲解永远以第三章版本为主。它的每一步都能单独解释清楚面试官跟上思路的成本低。如果你愿意可以在讲完主方案后补一句如果把反转动作提前到快慢指针遍历过程中还能省一点常数时间。说完再画出指针状态图对面会认为你确实理解得深而不是只会背代码。6. 边界条件与踩坑复盘从测试用例到“恢复原链表”6.1 必测用例清单我刷链表题养成了一个习惯写完第一版代码先不着急提交先把边界用例在心里过一遍。回文链表这道题至少要覆盖这些情况用例期望结果容易出错的点空链表[]True很多人忘记判空直接访问head.next单节点[1]True同上两相同节点[1,1]True快慢指针和反转逻辑必须能覆盖长度 2两不同节点[1,2]False比较逻辑不能越界奇数回文[1,2,3,2,1]True中间节点是否被重复比较偶数回文[1,2,2,1]True偶数长度下slow是否指到正确位置非回文[1,2,3,4,5]False比较循环终止条件是否正确很多看起来“差不多”的代码在这些用例里至少会翻车一两个。我自己就写过一版快慢指针循环条件用错导致死循环的代码——while fast.next and fast.next.next在链表长度为奇数时快指针可能在某个时刻变成None下一轮循环访问fast.next就直接报错。稳妥写法永远是while fast and fast.next。6.2 一个被很多人忽略的问题函数结束后链表被破坏了第三章和第五章的解法都会反转一部分链表也就是说调用isPalindrome之后原链表不再是原来的样子。LeetCode 在线评测不检查这一点所以很多人从没注意过。但面试官很喜欢顺着这个点往下问。举个例子用第三章的反转后半段方案处理1 - 2 - 3 - 2 - 1比较结束后原链表从头部开始已经变成了1 - 2 - 3 - None后半段整体被割裂了。如果调用方在判断完回文后还要继续遍历这个链表做别的操作就会出问题。在实际工程里“函数副作用越小越好”是一个重要原则。所以比较完恢复原链表是体现工程意识的好加分项。6.3 恢复方法反转后半段版本其实很好修如果你用的是第三章“反转后半段”方案恢复原链表只需要记住一个变量比较开始前的right头节点。比较结束后再对right做一次反转后半段就变回原来的顺序同时它和前半段在中间节点处会自然接回。# 比较之前记录后半段反转后的头 right_head prev # ... 双指针比较代码 ... # 比较结束后恢复后半段 reverse(right_head)为什么这样就能恢复因为第一次反转把后半段3 - 2 - 1变成了1 - 2 - 3再次反转又会把1 - 2 - 3变回3 - 2 - 1。而原链表的前半段1 - 2 - 3中节点2的next仍然指向中间节点3中间节点恢复成右半段头之后整条链表就重新连起来了。这个细节我第一次没想明白后来在本地打印链表状态才彻底看透。第五章的“边找中点边反转前半段”方案恢复起来就麻烦得多因为前半段已经被拆散了等于是把好几个节点的next都改了再想逐个还原需要额外记录不少中间状态。这也是我不建议面试首选它的原因之一。6.4 本地调试小习惯写一个打印链表的辅助函数链表的指针操作肉眼网格看代码很容易出错但打印出来一眼就能看出断链在哪。我调试链表题时会写一个很简单的辅助函数把链表转成 Python 列表def to_list(head): result [] while head: result.append(head.val) head head.next return result然后在快慢指针找完中点后、反转之后、比较之前分别打印一次看看当时链表长什么样。这种方式比在脑子里空转指针高效得多尤其是处理“恢复原链表”这种问题打印前后对比几乎是唯一可靠的排查手段。比如处理1 - 2 - 2 - 1时找完中点后打印to_list(head)可以看到前半段反转后半段后打印to_list(right)会得到1 - 2比较完成后再次打印to_list(right_head)又能看到恢复成了2 - 1。有了这些中间状态指针错位的问题基本不会藏过十分钟。这道题我前后刷过好几遍每一遍都有新体会。第一次只会用数组第二次写出栈版本第三次才真正理解“原地反转”为什么是链表题的灵魂操作。回文链表的解法其实就是在反复强调一件事链表不能随机访问但你可以通过改变指针方向把“倒序”转换成“正序”。如果你也在刷链表题建议拿到题目先问自己三个问题空间限制是多少、原链表能不能破坏、需不需要恢复原状。把这三个问题想清楚代码基本就不会跑偏。最后再分享一个小技巧凡是涉及反转链表的题目只要每一步都画出“当前节点、前驱、后继”三个指针的位置你就能避开绝大多数指针bug。