回文链表最优解：快慢指针+反转链表，O(1)空间判定

回文链表这道题在LeetCode上是编号234的经典题但凡是准备面试刷题的人几乎都会把它放进必刷清单。我当年第一次看到这道题内心是有点不屑的——回文不就是正着读和反着读一样吗数组的话直接双指针从两头往中间走就行链表嘛转成数组不就完了结果真在面试里被面试官追问了一句“能不能O(1)空间复杂度做”我当场就卡壳了。后来把这道题彻底吃透才发现它考的不是“回文”这个概念而是链表操作里最核心的快慢指针、反转、断开连接这些基本功的组合运用。这篇文章把这题从朴素解法到最优解法的完整链路讲清楚顺便把那些网上题解很少提到的边界坑和面试扩展点也补上希望对正在刷题的朋友有帮助特别是那些刷到“反转链表”和“链表中点”还不太熟的人这篇就是为你们准备的。1. 回文链表到底在考什么先看题目本质1.1 题目描述与核心约束LeetCode 234回文链表的原题是这样的给定一个单链表的头节点head判断这个链表是否为回文链表。题目有两个要求第一是在 O(n) 时间内完成第二是 O(1) 额外空间完成进阶要求。如果是空链表或者只有一个节点直接返回 true。第一个约束 O(n) 时间其实是所有链表题目的“保底条件”因为链表本身就是线性的你无论如何都得遍历一遍才能看完所有节点。真正的难点是第二个约束——O(1) 额外空间。这个约束直接堵死了“把链表转成数组再判断”这条最直觉的路。很多人的第一反应就是把链表遍历一遍把值存进数组或列表然后用双指针从两端往中间比较。这个思路很自然但它有一个致命问题空间复杂度是 O(n)。当面试官告诉你链表长度可能有上百万个节点时这个方案就废了。所以这题真正考察的是在不能使用额外数组存储所有节点值的前提下能不能靠改变链表本身的访问顺序来完成回文判定。1.2 单向链表的天然劣势要理解这道题的难点得先回忆一下链表的基本特性单链表每个节点只保存了指向下一个节点的指针你不能像数组那样用下标直接定位到任何位置的元素。数组的回文判断之所以简单是因为 arr[0] 和 arr[n-1] 可以同时被 O(1) 访问但链表你要访问最后一个节点就得从 head 一路走到尾O(n) 的访问时间。如果对每一对对称位置都这样操作总复杂度就会变成 O(n^2)这明显不能接受。所以核心矛盾就是我们既要按“从两端往中间”的顺序来比较节点值又不能真的去“随机访问”链表的尾部。那怎么办一个很自然的思路是——把链表从中间劈开让后半段能够从后往前遍历。这个思路的落点就是“反转快慢指针”也就是这道题的标准解法。2. 先写一个保底版本转数组双指针2.1 写法与复杂度学习任何算法题我都不建议直接跳最优解而是先有一个能跑通的保底方案。对于回文链表最简单直接的版本就是遍历一次链表把所有节点的值存进一个动态数组然后对数组做双指针比较。class Solution: def isPalindrome(self, head: Optional[ListNode]) - bool: 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)存了 n 个元素。它能在绝大多数评测用例下通过代码简洁也不容易写错。我用这个版本给身边的初学者讲题时很多人第一反应都是“这不就完了吗为什么要折腾快慢指针”这时候我就会让他们把代码里的vals去掉试试——一旦去掉代码瞬间就没了存储回文的凭证这正是接下来要面对的关键问题。我把这个保底版本叫“入门保底版”因为它能帮你快速通过题目但它绝对不是面试的终点。面试官真正想看的是你面对“空间限制”时的思考路径而不是你背下来的最优解模板。所以哪怕你最终可以写出最优解也建议先在心里把数组版本推演一遍——它能帮你确认自己对回文定义的掌握是没有问题的然后再去考虑空间上的优化。2.2 数组版的两点经验第一这个版本在大多数编程语言里都能轻松实现因为语言自带的动态数组Python的list、Java的ArrayList可以随意扩展不需要你管理内存。第二它的主要价值是“对照基准”——后面写出快慢指针反转版本后你可以用数组版来交叉验证确保两组代码对同一组输入产生完全一致的输出。我实际做题时经常先用数组版跑一遍标准case再换成最优解跑一遍如果结果有出入一定是新版本写错了这样可以快速定位bug避免在边界条件里打转。不过数组版有一个小坑当链表的 val 值非常大比如超过语言普通整型的表示范围时数组版也在内存中保存这些大对象的副本。虽然 LeetCode 的用例一般不会如此极端但在真实的嵌入式环境中“存副本”这种做法本身就是一种奢侈。这个点先按下不表后面会详细说为什么 O(1) 空间在实际工程里有意义。3. 最优解拆解快慢指针找中点 反转后半段3.1 核心思路的三个分步O(1) 空间版本的基本思想只有一句话找到链表的中点把后半段原地反转然后从两端同时开始比较。把它拆开就是三个子问题找到链表的中点同时保留 head 以便后续比较反转中点到尾节点之间的那部分链表同时遍历前半段从 head 出发和反转后的后半段逐节点比较这三个子问题分别对应了链表操作的三个常用基本功快慢指针找中点、反转链表、循环遍历比较。你在刷题时如果对这三个基本功都烂熟于心那这道题的代码就是一次拼接的功夫。但如果其中任何一步不熟练做题时就会卡住。我先说为什么选“反转后半段”而不是“反转前半段”。从直觉上讲回文判断需要从两个端点向中间移动。反转前半段的话你虽然能从头部向中间方向进行“反向遍历”但是反转后head 位置就变成了尾节点你还需要额外记录原本的头节点位置操作起来别扭。反转后半段则非常自然head 保持原位后半段的“头”变成了原来的尾比较过程就是从原 head 往后走、从原尾往回走两边在中点会合。这样代码逻辑最清晰也最容易向面试官解释。3.2 快慢指针找中点的两种常见写法快慢指针找中点是这个解法的第一步很多人在这一步就出岔子根本原因在于对“中点”的定义混乱。链表长度为奇数时中点是一个确定的节点长度为偶数时“中点”实际上是两个中间节点之一。在回文链表的场景里我们真正关心的是把链表从中间断开左半段和右半段的起始节点分别是什么。我最常用的写法是slow head fast head while fast and fast.next: slow slow.next fast fast.next.next # 循环结束后slow 指向链表中点偶数长度时指向右半段的第一个节点这个写法里slow 每次走一步fast 每次走两步。当循环结束时对奇数长度链表slow 正好落在正中间对偶数长度链表slow 落在右半段的第一个节点。举个例子链表 1-2-3-4-5循环结束后 fast 先走到 None此时 slow 停在 3链表 1-2-3-4 呢我们带一下循环初始三个指针都在 1第一次迭代 slow 到 2fast 到 3第二次迭代 fast.next4fast.next.nextNone因此条件二 fast.next 仍为真进入循环slow 到 3fast 等于 None因为 fast 本来是 3fast.next 是 4fast.next.next 是 None所以 fast 被赋值为 None。循环结束slow 指向 3——正是右半段的第一个节点。这个结果对我们非常有用因为回文判断中左半段是 1-2右半段是 4-3反转后变成 3-4。另一种写法是把 fast 初始化为head.next这样循环条件变成while fast and fast.next但我用过之后发现两个指针起点不同时奇偶情况下的中点位置会略有不同反而容易搞混。所以我个人的建议是初始都把两个指针放在 head循环条件用fast and fast.next这样语义最统一。3.3 反转后半段的细节找到中点后我们需要反转从 slow 开始到链表结束的这一段。这一步直接可以复用标准的“反转链表”代码也就是经典的迭代反转def reverse_list(head): prev None cur head while cur: nxt cur.next cur.next prev prev cur cur nxt return prev在回文链表中调用它就是second_half_head reverse_list(slow)。这里的second_half_head是反转后的后半段的新头节点——在原链表中它是最后一个节点反转后它变成了右半段的第一个节点。这里有一个容易忽略的细节反转后半段之后原链表的结构被破坏了。左半段的最后一个节点原本指向中点或右半段第一个节点现在它仍然指向那个位置但那个位置已经是右半段的“尾部”了。所以如果你在比较完之后还想保留原链表就必须在返回前再把后半段反转一次恢复原结构。LeetCode 题目本身不要求恢复很多题解也不提这点但如果你参加的是面试面试官很可能会追问“你的算法修改了原链表如果调用方不允许修改呢”。这种情况我在后面专门展开聊。4. 完整代码、边界案例与不用恢复链表的情况4.1 可以直接用的Python实现把上面的步骤拼在一起就是最优解。我给出一个可以直接跑通的版本注释写得很全class Solution: def isPalindrome(self, head: ListNode) - bool: # 1. 空链表或单节点直接返回 True if not head or not head.next: return True # 2. 快慢指针找中点 slow head fast head while fast and fast.next: slow slow.next fast fast.next.next # 3. 反转后半段 prev None cur slow while cur: nxt cur.next cur.next prev prev cur cur nxt second_half prev # 4. 前半段与后半段逐一比较 first_half head while second_half: if first_half.val ! second_half.val: return False first_half first_half.next second_half second_half.next return True注意这段代码里的第四步比较循环的判断条件是while second_half而不是while first_half。为什么因为右半段是整个链表的“尾巴部分”在反转后它的长度等于左半段或比左半段少一个节点两种情况。我们之前的分析里奇数长度时 slow 指向中点反转后半段后second_half包含中点和之后的所有节点它的长度比左半段多 1偶数长度时second_half长度等于左半段。那么用while second_half会不会在奇数长度时对中点本身做无意义的比较呢不会因为奇数长度时中点本来就是左半段的最后一个节点与右半段反转后的最后一个节点之间的“重合点”它和它自己比较总是相等的所以多比较一个节点不影响结果。而用while second_half可以保证循环终止在右半段走完的时刻避免first_half可能还未走完时出现空指针问题。4.2 逐个边界案例的实测记录我在本地测试时会按这几个 case 逐一过一遍确保没有遗漏输入链表期望输出实测结果备注NoneTrueTrue空链表代码开头已经判空1TrueTrue单节点返回 True1-1TrueTrue偶数长度最短回文1-2FalseFalse偶数长度非回文1-2-1TrueTrue奇数长度回文会多比较中点1-2-2-1TrueTrue经典偶数长度回文1-2-3-2-1TrueTrue奇数长度回文最大链长可以加大验证1-0-1TrueTrue值有 0 的情况也需要验证其中最容易出错的 case 是1-0-1这种含 0 的因为在 Python 里 0 在布尔上下文里等同于 False。如果第四步循环条件写的是while first_half and second_half:且没有显式判断 val当值本身是 0 时比较逻辑依然正确但如果你在循环里写了类似if not first_half.val and not second_half.val这样的逻辑就会被坑。我的建议很朴素比较 val 只用等号不要依赖布尔语义。再补充一个容易犯的错快慢指针的循环条件while fast and fast.next里fast.next这个访问只有在fast不为 None 时才安全。为什么这个顺序不能颠倒因为 Python 的and是短路求值的先判断fast为真才继续判断fast.next。如果把两个条件反过来写成while fast.next and fast当 fast 恰好为 None 时会报AttributeError。这个坑我曾经在面试者代码里见过虽然正规写法大家都知道但面试紧张时真的可能写反。4.3 关于“是否恢复链表”这个经典追问LeetCode 的评测只关注返回值所以上面那段代码不恢复链表也能通过。但在真实面试中面试官有八成概率会追问一句话“这个算法对原链表有副作用如果调用方需要链表保持原样怎么办”我第一次听到这个问题时愣了一下后来总结出一个标准方案比较结束后再执行一次反转把后半段恢复原状。具体的做法是把反转后半段时的引用存起来比如reversed_half prev比较完之后执行reverse_list(reversed_half)把后半段恢复了。这样原链表就完全保持原样。# 比较结束后恢复原链表 reverse_list(reversed_half)这个恢复操作的时间复杂度同样 O(n)但注意它不影响大 O 结果仍然是 O(n) 时间、O(1) 空间只是常数翻倍。如果面试官追着问“为什么倍数不是关键”你要能答出一句“O(n) 的那个 n 是线性增长的常数2在极限意义下仍属于O(n)”这样面试官对你概念的掌握会留下不错的印象。我实测下来恢复链表和不恢复链表LeetCode 的通过结果没有差别题目本来就不检查链表结构但如果你能在代码里主动补上恢复操作面试观感会明显更好——这体现的不是“你会背题”而是“你考虑到了调用者的使用环境”。5. 为什么 O(1) 空间在工程里不是矫情5.1 从“我能通过评测”到“我能用于生产”的距离很多初学者觉得 O(1) 空间要求很“刻意”明明数组版又短又直白为什么非要用快慢指针反转这种绕来绕去的做法我用一个实际的工程场景来回答这个问题。假设你在一家做嵌入式设备的公司工作设备的内存只有几十 KB运行着一个实时操作系统。你要判断某个通信协议里收到的一段数据链是否为回文结构。这段数据链是以链表形式组织的这在底层驱动里很常见它的长度可能达到几万节点。如果你用“转数组”的思路先申请一块容量等于节点数的缓冲区那么在内存本身就紧张的环境里这个过程很可能直接触发内存不足或导致系统卡顿。而 O(1) 空间的算法只需要固定几个指针变量无论链表多长额外内存占用都是常量。这种场景虽然离日常的 LeetCode 较远但确实是真实存在且值得在意的地方。这一点放在更大规模的系统里也一样成立。现代服务器虽然内存很大但当你处理几百万条链表数据时额外 copy 一份数组就可能是几百 MB 到上 GB 的内存占用这在性能敏感服务里是不可接受的。所以说 O(1) 空间的算法不是刷题专用的“雕花技巧”它在资源受限或者性能敏感的工程环境里是一种具备现实价值的思维方式。5.2 “数组版 vs 指针版”一组直观对比维度数组版快慢指针反转版时间O(n)O(n), 常数略高多一次反转移位空间O(n)O(1)代码量较少较多对原链表影响无修改原链表需额外恢复适合场景内存充足、快速验题面试展示、嵌入式/大数据场景用这张表给朋友讲题时我通常还会补一句数组版的价值在于“容易验证你的思路是否正确”而指针版的价值在于“展示你在约束条件下解决问题的能力”。这两种能力在工作中的对应关系也很直观——前者像是“先写出能跑的版本”后者像是“在资源受限时仍然保证可靠性”。6. 面试官视角这道题的考察点与常见陷阱6.1 面试官真正在意的三件事我陪朋友做模拟面试的时候经常扮演面试官的角色这道题我问过的人不下二十个。回文链表这个题目有意思的是它没有一个刁钻到普通人想不到的算法而是需要把几个“你会但未必熟练”的基本功组合起来。那面试官真正在意的往往是以下三点第一能不能主动识别出“ O(1) 空间”这个约束并且立刻调整思路。很多人一看到回文脑子里只有数组双指针连“链表没有反向遍历”都没意识过来这就说明对链表基本功不熟。第二快慢指针边界条件的准确性。我刚带过的人里将近一半会在链表长度为奇数或偶数时把 slow 的位置判断错然后导致反转了错误的半段。第三是否能处理“修改原链表”导致的副作用问题。这个问题不在工位上写不出来但一旦面试官引导你如果能立刻说出“那我在结束后反转回来”印象分会明显升高。6.2 一个隐蔽的细节fast 指针的遍历终点在快慢指针的循环里循环结束的时机意味着什么对一个奇数长度链表比如 5 个节点fast 的移动路径是 1-3-5-None此时fast为 None循环结束。对于一个偶数长度链表比如 4 个节点fast 的路径是 1-3-None此时虽然 fast 是 None但循环条件判断fast and fast.next时由于 fast 已经是 None条件为假循环照样结束。这与我们前面定义的中点目标完全一致奇数长度时 slow 在正中间偶数长度时 slow 在右半段开头。这个细节的实操价值在于如果你手写代码时把循环条件写成while fast.next and fast.next.next在偶数长度时 fast 会在倒数第二步变成 None 但被你提前判断可能导致循环提前一轮退出slow 停的位置就不对了。所以做题时一定用while fast and fast.next这个标准写法不要自己“优化”成奇怪的版本。6.3 常见错误模式清单我把自己见过的错误模式整理成一个清单方便你自查对空链表或单节点没有单独处理导致快慢指针循环里出现空指针。实际上 LeetCode 的默认测试用例可能包含空链表如果你代码里没有if not head or not head.next: return True可能在极端 case 下直接异常。快慢指针从不同的起点出发比如 slow 初始为 headfast 初始为 head.next。这会导致中点偏一个位置后续反转的区间随之错误比较结果就是错乱。除非你明确知道某一种写法的语义否则统一用同起点最稳。反转后半段时没有保存下一节点nxt cur.next就直接将cur.next prev导致链表断裂循环直接死循环或抛异常。这是反转链表永远排在第一位的基础问题。比较循环里错误使用了while first_half and second_half而不是while second_half。在奇数长度时first_half和second_half同时存在但第一个半段会先走完导致漏比较或空指针。稳妥的做法是以second_half为循环条件因为右半段长度是我们掌握得最清楚的。忘记考虑节点值为负数或 0 的场景。对布尔语义的依赖会导致逻辑错误一定要在比较时显式用!判断值。我建议你把这段清单背下来不是为了背答案而是为了在做题时形成条件反射发现错误时能立刻定位是哪一类问题。我在带刷题的过程中发现很多人卡住的不是“不会最优解”而是“边界 case 想不周全”。把边界情况做成清单遇到测试报错先对照清单查远比凭空猜要快。7. 从回文链表延伸出去变体与关联题7.1 如果题目变成 O(1) 空间且不允许修改链表我在面试模拟中还遇到过这样的变体要求 O(1) 空间但原地不能改链表。这种条件下快慢指针反转的方案就失效了因为你不能反转后半段。那怎么办此时可以递归走到链表尾再通过“递归回退”来模拟从尾到头访问。不过递归需要系统栈严格来说空间是 O(n) 的。如果题目真的要求 O(1) 空间且不允许改结构那就没有纯理论上的解了只能通过“每比较一对位置就从头走一遍”的方式做时间复杂度会退化成 O(n^2)。这类变体的意义在于提醒我们“限制条件”和“时间复杂度”之间的权衡关系面试时你也可以主动向面试官说明这种权衡。7.2 与环形链表、反转链表、链表中点的关系回文链表和另外几个高频题直接相关环形链表判断链表中是否有环也常使用快慢指针反转链表更是回文链表的核心步骤而“找链表中点”本身在有序链表转平衡二叉树、合并排序等问题中也会反复出现。换句话说回文链表把「快慢指针」「反转链表」两颗基本的“技能树”做了一个复合考察。如果你能把回文链表吃透这三个基础技能你会一并练到之后遇到依赖这些技能的题目会轻松很多。7.3 使用扩展技巧一边遍历一边反转比较我最近看到一个更进阶的玩法不用先找中点再反转而是使用快慢指针的同时把 slow 走过的前半段逐步反转。这样当 fast 走到链表末尾时前半段已经变成了“从尾到头的形态”而后半段保持原序直接从头开始比较即可。这个思路代码更短但理解起来不如“先找中点再反转整段”直观而且非常容易在边界上写错。刷题练习时我不建议一上来就挑战这个版本先把标准版本写熟理解每一步的目的再考虑这种“边走边反转”的写法。顺带提一句这个思路在某些语言的实现里还牵涉到内存别名的问题如果处理不当可能会导致某个节点被重复使用甚至产生环。我在实践时发现它虽然是可行的但调试复杂度明显高于“找中点后反转整段”所以我个人的建议是面试时优先用解法清晰、容易证明正确性的版本而不是炫技。面试官最看重的是你能否在约束条件下做出一个正确、可解释的方案。8. 实操总结与我的刷题心得回文链表这道题刷一遍肯定是不够的。我建议你至少写三遍第一遍用数组版跑通第二遍用快慢指针反转版跑通第三遍加上“恢复链表”的逻辑重新跑。三遍之后你对链表操作的肌肉记忆会比死记硬背牢固得多。在这道题上我个人的一个习惯是“纸上先画图再写代码”。遇到链表题先画一个 5 节点和 4 节点的示意图然后在图上模拟快慢指针移动、反转指针指向等图上的每一步都对上了再动笔写代码。这种方法虽然看起来慢但实际上比直接在编辑器里边写边改快得多因为它能在动手之前就解决掉一大半边界问题。另外我强烈建议你在写完代码后顺便用一个小小的“恢复原链表”的测试来验证代码正确性。做法很简单在调用isPalindrome之后打印出链表的前几个值检查它们是否和输入一致。这个动作能非常快速地暴露你反转逻辑里的隐性 bug也能让面试官看到你考虑问题的周全程度。最后再分享一个把这道题进一步“吃干榨净”的方法把原链表改成双链表再写一遍这道题或者把原题改成“判断回文串字符串”并对比两种数据结构的差异再或者判断一个由链表表示的整数是否是回文。每一次变形都会逼着你重新思考“回文”和“数据结构”之间的关系而不是被动地背题。这个过程积累下来你不仅刷会了这一道题整个链表类型的题都开始变得有章法了。