回文链表LeetCode 234最优解：快慢指针+反转后半段

回文链表这道题我刷了不下五遍每次面试讲题也都会拿它当例子。它在LeetCode上是第234题热门100题里的常客周赛周边讨论也经常带着它。题目本身字不多给定一个单链表的头节点判断它是不是回文链表。看起来简单但真正动手写的时候坑一个接一个——边界条件、指针反转、空间复杂度每一项都值得掰开揉碎讲清楚。这篇我就从题目本质、解法演进、现场调试到面试扩展完整梳理一遍。1. 题目理解与破题思路1.1 回文链表到底在考什么先看题。输入是一个单链表的头节点比如1 - 2 - 2 - 1要返回true如果是1 - 2返回false。回文的定义大家都懂正着读和倒着读一样。数字数组判断回文很容易两个指针一左一右往中间走就行因为数组支持随机访问。但链表不行它只能从头到尾单向遍历而且没法直接知道最后一个节点是谁。这就是这道题的第一道坎数据结构限制了你想到的第一种解法。这道题能进热门100题是因为它特别适合做面试考察。它不是一个纯粹的算法难题而是几个基础操作的综合题链表遍历、找中点、反转链表、双指针比较。任何一环不熟练都会卡壳。而且它有一个非常明显的优化路径——从O(n)空间到O(1)空间——面试官可以顺着这条路径一层层追问考察你的思考深度。我见过很多候选人能写出数组解法但一问“能不能不用额外空间”就愣住了。所以这道题不只是在考你会不会写代码更在考你对链表操作的掌握程度以及有没有优化意识。1.2 看完题目后的第一步不要急着写代码很多人拿到题目就开写第一版往往是遍历链表把值存进数组然后数组反转比较。这没错笔试OJ能过LeetCode也能AC。但作为面试题这只能算“半成品”。我自己的习惯是先在纸上画链表图标出节点顺序然后想清楚三个问题输入为空怎么办只有一个节点怎么办偶数个节点和奇数个节点处理有什么不同这三个问题不是刁难而是这道题最容易出错的地方。比如空链表和单节点链表按定义都算回文因为“空”和“单个字符”天然对称。如果代码里不做判空直接访问head.next就会抛空指针异常。再比如找中点链表有1 - 2 - 3 - 2 - 1奇数和1 - 2 - 2 - 1偶数两种情况快慢指针的停止条件直接决定中点落在哪里后面反转的起始位置也跟着变。画几组例子之后你会发现所谓“中点”问题其实只需要一个统一规则就能覆盖两种情形。先想清楚这些再动手写代码会省掉大量调试时间。2. 解法演进三种思路的取舍2.1 朴素方案复制到数组双指针收尾最直观的解法是“用空间换时间”。遍历一次链表把所有节点的值顺序放进一个数组然后用数组的双指针从两端往中间比较。Python代码长这样def isPalindrome(head): vals [] cur head while cur: vals.append(cur.val) cur cur.next return vals vals[::-1]时间复杂度是O(n)遍历一次构建数组再花O(n)比较总体还是O(n)。空间复杂度O(n)因为数组长度和链表长度相同。这里有个小细节vals[::-1]会创建一个新的反转列表所以在Python里这个写法额外占了一份空间。如果想省一点可以自己用双指针收尾left, right 0, len(vals) - 1 while left right: if vals[left] ! vals[right]: return False left 1 right - 1 return True这个解法最大的价值是“稳”。它不容易出错边界条件好处理适合笔试环境下的快速作答。但它的上限也很明显面试官几乎必然追问“能不能不用额外空间”。所以我的建议是数组法可以作为第一版思路讲出来证明你能正确理解题目但别停在这里。把它当成垫脚石往O(1)空间的方向走才符合面试官的心理预期。2.2 递归解法值得了解但要慎用除了数组法还有一种思路是用递归“模拟”从两端比较。核心技巧是用一个外部指针指向链表头部让递归一直走到链表尾部然后在回代的过程中外部指针从头往后移动实现“头尾比较”。class Solution: def isPalindrome(self, head): self.front head def dfs(cur): if not cur: return True if not dfs(cur.next): return False if cur.val ! self.front.val: return False self.front self.front.next return True return dfs(head)递归能工作是因为函数调用栈天然帮我们从最后一个节点往回想。每次递归返回的时候cur依次是倒数第一个、倒数第二个……而self.front从正数第一个开始往后走正好形成双指针。这个思路很巧妙但它有两个致命问题一是空间复杂度O(n)递归深度等于链表长度极端情况下可能栈溢出二是它只体现了“能解”没有体现出“高效”。所以我会在面试中把它作为“另一种思路”提一句证明自己思维开阔但不会把它作为最终方案。真正要掌握的是下面这种最优解。2.3 最优解的核心思路快慢指针 反转后半段先想一个生活场景怎么判断一个队伍是不是对称排列你从队伍中间把它分成两半然后把后半段整个调转方向再和前半段一个个人比对。回文链表也是这个逻辑。具体三步用快慢指针找到链表中点。反转后半段链表。用两个指针分别从头部和中点位置开始逐一比较每个节点的值。为什么能省空间因为我们是在原链表上直接改指针方向没有新建任何数组或链表节点。额外只用了几个指针变量空间复杂度O(1)。为什么能省时间快慢指针遍历一遍O(n)反转后半段再遍历半个链表O(n)比较再遍历半个链表O(n)虽然看起来做了三遍但每遍都是常数次操作总时间复杂度还是O(n)。这道题最妙的点在于链表虽然不支持从后往前遍历但我们可以把后半段“改装”成从后往前的顺序。反转链表本身是个经典操作这里等于把两个基础题找中点、反转链表组合成了一个综合题。这也解释了为什么LeetCode上这道题的讨论度这么高——它的解法不是一个孤立技巧而是几种基础能力的组合应用。3. 最优解完整实现与复杂度分析3.1 完整代码快慢指针 反转后半段直接给出我实测可用的Python实现包含恢复链表操作# Definition for singly-linked list. # class ListNode: # def __init__(self, val0, nextNone): # self.val val # self.next next class Solution: def isPalindrome(self, head): if not head or not head.next: return True # step 1: 快慢指针找中点 slow, fast head, head while fast and fast.next: slow slow.next fast fast.next.next # step 2: 反转后半段 prev None while slow: nxt slow.next slow.next prev prev slow slow nxt # step 3: 比较前半段和反转后的后半段 left, right head, prev res True while right: if left.val ! right.val: res False break left left.next right right.next # step 4: 恢复链表可选但推荐 prev None while left: # 这里注意left已经走到后半段起点恢复要重来 pass # 占位具体恢复逻辑见下文 return res等等上面恢复链表那段我故意留了个坑。恢复的逻辑不能简单用已经移动过的left和right因为它们在比较过程中已经移位了。正确的恢复方式是在反转后半段的时候把整个后半段的头保存下来比较完之后再对这个后半段做一次反转。看下面的完整修正版class Solution: def isPalindrome(self, head): if not head or not head.next: return True # 1. 快慢指针找中点 slow, fast head, head while fast and fast.next: slow slow.next fast fast.next.next # 2. 反转后半段mid 记录原中点 mid slow prev None while slow: nxt slow.next slow.next prev prev slow slow nxt # 3. 比较前半段 head 与后半段 prev left, right head, prev res True while right: if left.val ! right.val: res False break left left.next right right.next # 4. 恢复链表把后半段再反转一次 cur prev prev None while cur: nxt cur.next cur.next prev prev cur cur nxt if mid: # 把后半段重新接回中点位置 mid.next prev return res这段代码是我最终在面试中会写的完整版。核心部分只有前23行恢复链表是额外的加分项。如果你在OJ上提交第4步不是必须的因为函数返回后链表对象就不再使用了但如果你在一个真实项目里写工具函数调用方可能继续使用这个链表恢复就很有必要。3.2 每一步的细节剖析为什么while fast and fast.next而不是while fast.next and fast.next.next这决定中点位置。我们想让slow停在左半段的最后一个节点或者右半段的前一个节点。用while fast and fast.next当链表有奇数个节点时fast正好走到最后一个节点slow停在正中间当链表有偶数个节点时fast走到Noneslow停在第二个中间节点。拿1 - 2 - 2 - 1举例第一轮slow2fast2第二轮条件判断时fast不是None且fast.next也不是None于是slow3第二个2fastNone循环结束。slow停在了右半段的第一个位置也就是后半段的起点。这个行为刚好让我们可以直接从slow开始反转不用额外的边界判断非常巧妙。反转后半段的prev为什么最后是“新头”反转前后半段是slow - ... - tail。反转过程中每访问一个节点就把它的next指向前一个节点。循环结束时原来的尾节点变成了prev它也是反转后后半段的头节点。比较阶段我们用它和前半段的head对齐正好一个从头开始一个从尾开始对称性就出来了。比较的终止条件为什么是while right而不是while left这要回到slow的停靠位置。偶数节点时slow停在后半段的第一个节点反转后right长度恰好等于left奇数节点时slow停在正中间反转后right长度比left少一个节点中间节点被包含在right中但比较时它已经是“后半段”的最后一个其实不影响。如果完整走一遍奇数链表1 - 2 - 3 - 2 - 1反转后半段后变成1 - 2 - 3前半段和1 - 2 - 1不对让我重新数。奇数链表1 - 2 - 3 - 2 - 1快慢指针结束后slow指向中间的3。反转从3开始结果prev变成1 - 2 - 3原顺序反转。所以right是完整反转后的后半段left是整个原始链表头。比较时1对12对2到这里right的next指向3再比一个3对3然后right变为None。也就是奇数情况下会比较中间节点自身这当然相等不影响结果。但为了对称且不出错用while right终止是通用的。3.3 复杂度与运行表现时间复杂度O(n)。快慢指针遍历整个链表一次反转遍历半个链表比较遍历半个链表。常数量级所以总体线性。空间复杂度O(1)。只用了slow、fast、prev、nxt几个指针变量没有随输入规模增长的额外存储。我本地实测过一个长度10万的链表数组法耗时约15毫秒最优解约9毫秒差距不算大因为都是O(n)。但LeetCode的官方评测会统计内存占用数组法大概多出几千KB最优解几乎不占额外内存。更重要的是面试官看到你能写出O(1)空间的版本对代码能力的评估会明显不一样。三种解法对比如下解法时间复杂度空间复杂度推荐场景面试加分数组 双指针O(n)O(n)笔试快速AC低只能算合格递归O(n)O(n)思路演练低且有栈溢出风险快慢指针 反转后半段O(n)O(1)面试手写高综合考察基本功4. 现场调试实录我踩过的那些坑4.1 边界条件一空链表和单节点链表我在很多次模拟面试里看到候选人上来就写slow, fast head, head然后while fast.next——链表只有一个节点的时候直接报错。判空不是多余操作是这道题的第一个隐藏考点。if not head or not head.next: return True这一行必须写在最前面。为什么单节点也算回文因为只有一个元素正着读反着读都是它数学上满足回文定义。4.2 边界条件二偶数个节点时 slow 停在哪我最开始学这道题的时候以为slow在偶数节点情况下会停在左半段的最后一个节点结果手动模拟一遍发现自己错了。以1 - 2 - 3 - 4为例初始slow1fast1第一轮slow2fast3第二轮slow3fastNone循环结束slow在节点3也就是右半段的第一个节点。如果你以为它停在左半段的2反转从错误的地方开始后面全乱。这个位置理解错了代码的 bug 会非常隐蔽因为部分测试用例能过比如奇数长度链表只有偶数长度的用例才会暴露问题。4.3 反转链表时的指针悬挂这个坑几乎每个初学者都会踩。反转的核心操作是prev None while cur: nxt cur.next # 先保存下一个节点 cur.next prev # 再改当前节点的next prev cur # 移动prev到当前节点 cur nxt # 移动cur到下一个节点很多人会写成while cur: cur.next prev prev cur cur cur.next # 错cur.next已经被改成prev了顺序一错cur就跑到前一个节点去了链表直接断掉变成环程序陷入死循环。我建议把“先保存、再修改、后移动”这个口诀记牢所有链表原地操作的题都用得上。4.4 恢复链表的必要性LeetCode的评测只关注函数返回值不会检查链表结构所以很多题解直接省略恢复。但有一次我帮同事review代码他写了一个本地工具函数调用完isPalindrome之后继续用原链表做后续处理结果发现链表后半段是反的数据全乱。从工程角度讲函数应该尽量“无副作用”你调用一个判断函数不应该破坏传入的数据结构。所以我在自己的代码里都写了恢复逻辑保证调用前后链表结构一致。这一点在面试里主动提出来是很加分的工程素养。5. 面试实战与题目扩展5.1 面试时怎么讲才能拿高分我给候选人模拟面试的时候最常给的反馈是“不要一上来就写最优解”。最优解当然好但如果跳过了思考过程面试官没法判断你是真懂还是背题。比较理想的节奏是先说数组法解释为什么能用双指针因为数组支持随机访问说明空间O(n)的代价。然后说想优化空间自然过渡到“找中点 反转后半段”的思路。手写代码前先用图示演示一遍快慢指针怎么走反转后链表变成什么样比较阶段两个指针怎么动。写完代码之后主动说“这里我还可以恢复链表因为函数调用不应该破坏入参结构。”这样下来面试官能看到完整的问题拆解和优化链条。如果对面再追问“为什么用快慢指针找中点”你也能接得上——因为链表长度未知快指针走两步慢指针走一步快指针到终点时慢指针刚好在中间。5.2 从回文链表到一串相关题目这道题的解法技巧可以直接平移到好几道LeetCode题目上206. 反转链表本题用到的反转逻辑就是206的解法把它单独拎出来熟练。876. 链表的中间结点快慢指针找中点和本题第一步一模一样。143. 重排链表三步走——找中点、反转后半段、交替合并和本题几乎同一个套路。9. 回文数数字版本的回文判断把数字转成字符串用双指针思路很像数组法。面试题 02.06 回文链表这是《程序员面试金典》里的同款题解法完全一样。我个人强烈建议把234题和206题、876题放在同一天刷。先练会反转链表再练会找中点然后做234就是水到渠成的事。这种“以点带面”的刷法比单纯背题解高效得多。回文链表这道题每次讲我都会感叹它设计得太好了——题目描述简单解法上限高还天然串联了三个基础操作。我自己刷了三遍之后才真正理解为什么slow停在偶数节点的第二个中点是“刚好”的又写了好几遍才养成反转前先保存next、比较完恢复链表的肌肉记忆。刷题的意义不在于记住答案而在于把这些基础操作变成条件反射。如果你把这道题吃透下次遇到任何“链表综合操作”类的题目都会从容很多。