空间实现)
先说我自己的一个切身体会。以前刷到回文链表这道题时第一反应是数组回文我会啊左右两个指针一夹逐个比较就完事了。可链表这东西只能顺着 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 是 tailfront 是 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 复杂度对比与选型逻辑用一张表把几种方案放在一起看方案时间复杂度额外空间是否修改链表代码复杂度面试评价数组复制O(n)O(n)否低能过但等待优化全量入栈O(n)O(n)否低思路直观半段入栈O(n)O(n)否中说明你理解快慢指针快慢指针反转O(n)O(1)是可恢复中高接近最优解递归回溯O(n)O(n)否中展示思路需注意限制注意表格里的“是否修改链表”一栏。快慢指针反转如果不恢复输入链表确实被改了。题目通常只看返回值但工程上“函数不要有意外副作用”是良好习惯所以我建议恢复。这也是为什么我在双指针法里专门加了恢复步骤它不改变复杂度但明显提升代码质量。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 断链的瞬间。 先说我自己的一个切身体会。以前刷到回文链表这道题时第一反应是数组回文我会啊左右两个指针一夹逐个比较就完事了。可链表这东西只能顺着 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 是 tailfront 是 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 复杂度对比与选型逻辑用一张表把几种方案放在一起看方案时间复杂度额外空间是否修改链表代码复杂度面试评价数组复制O(n)O(n)否低能过但等待优化全量入栈O(n)O(n)否低思路直观半段入栈O(n)O(n)否中说明你理解快慢指针快慢指针反转O(n)O(1)是可恢复中高接近最优解递归回溯O(n)O(n)否中展示思路需注意限制注意表格里的“是否修改链表”一栏。快慢指针反转如果不恢复输入链表确实被改了。题目通常只看返回值但工程上“函数不要有意外副作用”是良好习惯所以我建议恢复。这也是为什么我在双指针法里专门加了恢复步骤它不改变复杂度但明显提升代码质量。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 断链的瞬间。