刷链表题的时候我总喜欢先问自己一句这道题是在考操作还是在考思维LeetCode 234题《回文链表》两样都占。题目本身很直白给定一个单链表判断它是不是回文链表。1 - 2 - 2 - 1 是回文返回 true1 - 2 不是回文返回 false。可一旦面试官追加一句“能不能只用 O(1) 额外空间”很多人就卡住了。这道题非常适合所有正在刷链表专题的人尤其是校招、社招准备算法面试的朋友。它不涉及复杂的数学推导也没有各种高深数据结构但把快慢指针、链表反转、递归、空间复杂度分析这些高频考点全串了起来。说白了它是链表操作里最典型的“组合拳”题目。我最早刷这道题的时候第一反应也是“转成数组再用双指针”后来在模拟面试中被问了一句“如果链表有十万个节点呢”我才意识到这题真正要练的不是判断回文而是如何在 O(1) 空间里解决逆序访问问题。这篇文章我就从最朴素的解法讲起一步步拉到标准解法再分享一些我在实际调试中踩过的坑。1. 题目定位与朴素解法1.1 回文链表的本质难点先明确一下什么是回文链表。从概念上说“回文”指的是正着读和倒着读都一样比如 1 - 2 - 3 - 2 - 1。数字数组做这个判断非常简单两个下标从两端往中间走就行。但单链表不一样它只有 next 指针没有 prev 指针更不支持随机访问。换句话说你拿到了头节点可以一路往后走但想从尾节点往前走在单链表里是做不到的。这就是回文链表的本质难点判断回文天然需要“从两端往中间”或“从中间往两端”比较而单链表只给了一个方向的遍历能力。所以我们需要用一些额外手段比如先遍历一遍存到额外空间中或者把链表的后半段反转让后半段也能从尾到头方向访问。把这个本质想清楚刷题方向就明确了。后面不管用什么解法本质上都在解决同一个问题如何在不额外占用大量内存的前提下让链表后半段可被“从后往前”访问。1.2 用数组辅助判断笔试够用面试不够最简单、也最容易想到的解法是先把链表所有节点的值依次放进一个数组然后对数组做双指针判断。这个思路完全不碰链表反转也没有任何空指针风险。def isPalindrome(head): values [] cur head while cur: values.append(cur.val) cur cur.next left, right 0, len(values) - 1 while left right: if values[left] ! values[right]: return False left 1 right - 1 return True这段代码没有任何坑时间复杂度 O(n)空间复杂度 O(n)。你只需要额外存一份链表值的数组。我为什么说它“笔试够用”因为很多在线判题环境不会专门限制你使用 O(n) 额外空间尤其是 LeetCode 这类平台只要不超时、不超内存提交上去都能过。但如果是在面试里这只能算“起手式”而不是最终答案。面试官往往会追问能不能做到 O(1) 额外空间你可能还会想到另一个思路把整个链表反转一份然后与原链表逐节点比较。这也是 O(n) 空间因为单链表没有前驱指针你为了反转后还能拿到原链表必须复制一份完整链表或者先构造一个新串实际操作比数组更繁琐。所以相比之下数组方案已经是最清晰的暴力解法。2. 标准解法快慢指针 反转后半段2.1 核心思路为什么是快慢指针和反转题目的进阶要求是做到 O(n) 时间和 O(1) 额外空间。既然不能用额外数组我们只能从链表结构本身想办法。把回文链表的特征拆开看会发现一个规律链表的前半段和后半段是“镜像对称”的。如果能找到中间位置再把后半段反转那么后半段就会从原来的“尾部”变成“头部”这时候从链表头开始遍历前半段同时从反转后的后半段头部开始遍历两个指针一个往前一个往“相当于从尾部向前”的方向移动就能逐项比较。所以整个解法拆成四步用快慢指针找到链表的中间节点。反转中间节点之后的后半段链表。同时遍历前半段和反转后的后半段逐节点比较数值。如果愿意把后半段再反转回来恢复原链表。这里面最难理解的就是第一步为什么用快慢指针以及第二步反转之后链表会变成什么样。我逐个说。2.2 找中点奇偶长度不能踩坑找链表中点最常见的做法就是快慢指针快指针每次走两步慢指针每次走一步。当快指针走到链表末尾时慢指针正好走到中间。slow, fast head, head while fast and fast.next: slow slow.next fast fast.next.next循环结束后slow 的位置有两种情况链表长度是奇数slow 正好指向正中间那个节点。比如 1 - 2 - 3 - 2 - 1slow 会指向 3。链表长度是偶数slow 会指向中间偏右的那个节点。比如 1 - 2 - 2 - 1slow 会指向第二个 2。这个行为可以快速推导一下。假设链表有 4 个节点fast 初始在节点 1走两步后到节点 3slow 走一步到节点 2再判断一次fast 在节点 3 时有 next所以继续fast 走两步后为 nullslow 走一步后到节点 3也就是第二个 2。也就是说对于偶数长度slow 停在“右中点”。有一个非常常见的错误写法是用while fast.next and fast.next.next。这个条件在某些链表长度下会让慢指针停在错误位置尤其是只有两个节点的时候循环一次都不会执行slow 停在 head反转后半段时就会把整个链表后半段搞错。所以一定要用while fast and fast.next。还有一个边界要提前处理如果链表为空或者只有一个节点那一定是回文直接返回 true。否则后面 fast.next 可能会空指针。2.3 反转链表与逐对比较找到 slow 之后下面要反转以 slow 为头节点的后半段链表。反转操作是链表题的基本功每次都必须保证先保存 next 再改指针否则会断链。def reverse(head): prev None cur head while cur: nxt cur.next cur.next prev prev cur cur nxt return prev这个函数返回的是反转后新的头节点也就是原链表的尾节点。调用完second_half reverse(slow)后second_half 就是从后往前排列的后半段链表。比较阶段我推荐这样写first, second head, second_half while second: if first.val ! second.val: return False first first.next second second.next return True为什么不写成while first因为当链表长度是奇数时后半段反转后长度比前半段少一个节点。比如 1 - 2 - 3 - 2 - 1后半段反转前是 3 - 2 - 1反转后是 1 - 2 - 3而前半段从 1 开始是 1 - 2 - 3。比较过程first 从 1second 从 1相等。first 到 2second 到 2相等。first 到 3second 到 3相等此时 second.next 为 null循环结束。如果用while first比较完 null 后会尝试访问 first.val直接空指针。用 second 作为循环条件正好避开中间的重复节点因为后半段永远不比前半段长。2.4 复杂度与恢复链表这个解法的额外空间只有几个指针变量不随链表长度增长因此空间复杂度是 O(1)时间复杂度因为每个节点最多访问常数次整体是 O(n)。这才是 LeetCode 234 题真正想考察的点。但这里有个隐藏问题我们修改了原链表。LeetCode 的判题系统不会检查原链表是否被还原所以很多题解直接不恢复。但面试时如果面试官说“我不希望链表被破坏”你就需要多写一步恢复操作。恢复操作其实很简单比较结束后再调用一次reverse(second_half)即可。reverse(second_half)为什么这样就够了因为反转前半段时我们并没有断开前半段和 slow 之间的连接。前半段最后一个节点仍然指向 slow而第一次反转后 slow.next 变成了 null但 slow 后半段所在的链表被反转成了“尾到头”的顺序。第二次反转后后半段又重新变回“头到尾”并且头节点又是 slow。所以前半段末尾节点指向 slow 的关系依然成立链表自动恢复原样。你可能会觉得这个细节很难想明白。我第一次推导的时候也花了不少时间建议拿一张纸画一个奇数长度和偶数长度的链表把每个节点的 next 变化标出来跑两遍就通了。这块理解之后你对链表反转的掌控力会明显提升。3. 递归解法想象链表是一个回文结构3.1 递归回溯的核心写法除了反转后半段还有一种非常巧妙的思路利用递归天然的先深入后回溯把链表从尾部开始依次访问。这个思路不修改链表结构代码非常简洁但空间复杂度很高。实现方式是这样的在类里定义一个成员变量front指向链表头。递归函数先一路递归到链表末尾然后回溯时依次比较当前节点和 front 指向的节点每比较一次front 向后移动一步。class Solution: def isPalindrome(self, head): self.front head def check(node): if node is None: return True if not check(node.next): return False if node.val ! self.front.val: return False self.front self.front.next return True return check(head)这段代码的核心逻辑是递归到最深处时 node 是链表尾节点此时 front 指向头节点两个最外层的节点先比较然后递归回溯到倒数第二个节点front 已经移动到第二个节点再比较以此类推。这种解法对理解“链表的递归性质”很有帮助。你可以把 check(node.next) 这行理解成“先把后面的链表判断完再处理当前节点”本质上是用调用栈保存了每个待比较节点以此实现倒序遍历。3.2 递归的空间代价与适用场景递归解法的空间复杂度是 O(n)因为递归调用栈的深度等于链表长度。如果链表有几万个节点递归会非常危险轻则内存占用大重则直接栈溢出。所以在生产环境中我不推荐这种写法但在 LeetCode 题目本身的数据范围下它可以通过。另外有一个细节特别容易踩坑成员变量 self.front 必须在每次调用 isPalindrome 时重新赋值为 head。如果同一个 Solution 对象被多次调用上一次调用结束时 front 已经指向链表末尾下一次调用不重置结果一定不对。还有人说既然递归会保存调用栈那我用显式的栈不也一样吗确实可以用一个栈把所有节点值压进去再弹栈和原链表比较空间也是 O(n)。这类做法在思维上是朴素的也没有反转链表那么复杂但面试时不太加分因为和数组辅助法的空间复杂度没有本质区别。所以递归解法更适合作为“思路拓展”讲给面试官听证明你有多种角度理解链表但真正要写 O(1) 空间时还是得回到快慢指针 反转的迭代方案。4. 边界条件、测试用例与现场排查4.1 一定要跑的测试用例清单链表题最怕空指针和边界错误。回文链表这道题我非常建议你至少把下面这组用例跑一遍。不要只看“能不能通过”要边跑边调试观察 slow 的位置和反转后的链表长什么样。测试用例预期结果说明[]true空链表直接判 true[1]true单节点链表天然回文[1, 2]false偶数非回文[1, 1]true偶数回文最简单的双节点回文[1, 2, 1]true奇数回文中间节点不用管[1, 2, 2, 1]true经典偶数回文[1, 2, 3, 2, 1]true经典奇数回文[1, 2, 3, 4, 5]false非回文用来验证返回值[-1, 2, -1]true负数也可以正常比较[1, 0, 0, 1]true存在 0 值不影响比较超长链表比如 10 万节点全为 1true验证迭代解法不会爆栈[1, 2, 3, 3, 2, 1]true另一种偶数回文[1, 2, 3, 4, 3, 1]false后半段和前半段形状类似但不完全一致这些用例看起来简单但每一条都有针对性。比如 [1, 2] 用来验证两个节点时快慢指针是否正确[1, 2, 1] 用来验证奇数长度下反转后半段不会把中间节点算进去超长链表则专门攻击递归解法的栈空间问题。4.2 典型错误的定位方法我多次重写这道题总结出几个最典型的错误你可以照着自查。第一快慢指针条件写错。while fast.next and fast.next.next在偶数长度的短链表中会让 slow 停在头节点后续反转和比较全部错乱。解决办法就是固定用while fast and fast.next。第二反转时丢节点。写反转链表时如果先执行cur.next prev再取nxt cur.next拿到的 nxt 已经是 prev 了链表直接断掉。这个错误非常隐蔽尤其在你手忙脚乱的时候。建议把反转函数单独提取出来先保存 nxt再改指针三步顺序别乱。第三比较时用错循环条件。用while first在奇数长度回文上会越界访问 first.val。因为反转后的后半段比前半段少一个节点比较到后来 second 已经变为 nullfirst 还指向中间节点。用while second才是安全的。第四忘记恢复链表。如果面试里被问到口头解释“我可以在最后再反转一次恢复原链表”然后能写出对应代码就很加分。但如果你根本不知道为什么要恢复或者恢复时把指针接错反而暴露了对链表结构的理解不足。排查这类问题有一个很实用的方法写一个printList辅助函数在找完中点后、反转后、比较前各打印一次链表。观察 slow 的位置和 second_half 的第一个节点值是否跟预期一致。我刷链表题时几乎都会用这个调试手段比单步调试更快。5. 从刷题到面试讲清楚比做出来更重要5.1 面试官想听到的思路演进这道题在模拟面试中出现的频率很高因为它适合考查“从暴力到优化”的思维过程。如果你一上来就甩出快慢指针 反转的最优解面试官其实不好判断你是背题还是真懂。更好的表达方式是分层推进。你可以先说“这道题最直观的做法是转成数组空间 O(n)。”然后补一句“但既然链表本身不能随机访问我可以把后半段反转这样就能 O(1) 空间解决。”接着讲快慢指针怎么找中点、反转函数怎么写、比较时为什么用 second 作为循环条件。最后主动说“如果不允许修改链表我还可以再反转一次恢复。”这个过程中考官最想听到的是你对边界情况的理解比如奇数偶数长度、空链表、单节点。所以不需要着急写完所有代码先把思路分点说出来再动手写会显得更从容。我在模拟面试中发现很多候选人代码能过但一问“为什么偶数长度时 slow 在中间偏右”就解释不清。这个点是这道题的命门一定要练到能用一两句话讲明白快指针走两步慢指针走一步快指针能走的步数决定了慢指针最终的位置偶数长度时快指针最终停在 null 前慢指针自然落在右中点。5.2 延伸题与通用能力这道题做完之后不要急着删掉它后面还关联着一串高频题反转链表 II要求反转链表中某一段核心就是本题所用的反转函数。删除链表的倒数第 N 个节点用快慢指针找位置和找中点异曲同工。环形链表 II也是快慢指针只是多了一步数学推导。回文数这个用字符串或取余都可以和链表的解法思路不同但“镜像对称”的判断逻辑相似。如果你把回文链表这道题彻底吃透再去做这些延伸题会明显感觉链表题之间是相通的。所谓“刷题量”不是单纯刷了多少道而是能否把一道题里的操作抽象成可复用的能力。回文链表刚好把“快慢指针”和“链表反转”两个基础能力揉在一起值得多写几遍直到能无脑写对。我个人实际操作中的体会是写链表题千万不要只在脑子里想一定要画图。画得不精致没关系重点是标出每一步的指针指向变化。这道题我第一次在纸上画的时候用了十几分钟但画完之后整个状态就通透了。后面不管是写递归还是恢复链表都能顺着指针方向一步步推出来。如果你也经常被链表题卡住不妨试试这个办法比一味刷题更有效。