回文链表怎么判断？快慢指针加反转链表，O(1)空间搞定 LeetCode 234-北京尧图网络

1. 题目解读与思路拆解为什么这道题值得放进 Hot100回文链表是我在 LeetCode Hot100 刷到第 21 题时重点复盘的一道题。题目描述很简单给定一个单链表的头节点判断它是不是回文链表进阶要求在 O(n) 时间内和 O(1) 空间内完成。回文的定义大家都熟就像上海自来水来自海上放到链表里就是正着读和倒着读的值序列完全一样比如 1-2-2-1 是回文1-2-3 不是。这道题能被放进 Hot100 并不意外。表面上它只有一句话实际上覆盖了链表题最核心的几个基本功遍历链表、查找中间节点、反转链表。更妙的是它还逼你思考空间复杂度从 O(n) 优化到 O(1) 的完整路径这是很多简单题不会给你的层次。刷完这一题等于把链表双指针的核心套路整体过了一遍。我觉得适合来看这篇文章的有两类人一类是在按主题刷 Hot100 的求职者想把高频题真正吃透另一类是刚开始接触链表算法、总觉得指针指来指去容易晕的同学。下面我会先把整道题的思路脉络讲清楚再给两套可以直接用的代码最后把容易踩的边界和面试回答方式一起聊透。1.1 回文链表判断的本质把后半段折回来链表和数组最大的差异在于访问方式数组是随机访问链表只能顺着 next 单向移动。判断回文天然是想从两端向中间逐个比较所以最直接的做法不是从尾巴往回走而是想办法拿到后半段的逆序。只要你能把后半段反转过来问题就变成了同时遍历前半段和反转后的后半段逐个比较 val。理解了这个本质你就能自己推出解法而不是死记答案。最简单思路是把链表值全部复制进数组数组天然支持两头夹逼空间优化思路是不复制直接原地反转后半段。后面两套代码都是围绕怎么拿到后半段的逆序展开的主线非常清楚。1.2 四种常见解法横向对比我梳理了四种思路分别适合不同场景解法时间空间修改链表适用场景数组双指针O(n)O(n)否先保证正确快速 AC栈O(n)O(n)否理解后进先出的直观解法递归O(n)O(n)递归栈否理解递归思路工程不建议快慢指针反转O(n)O(1)会可恢复最推荐面试标准答案栈的思路很直白第一遍遍历把节点值压栈第二遍遍历时依次弹栈比较。它比数组多了一层后进先出天然逆序的语义但空间占用和数组没有本质区别。递归则是把从后往前的指针交给系统栈处理代码很简洁但链表稍长就容易爆栈所以我不会在正式场景里推荐它。真正需要掌握的是最后一种也是本文的重点。2. 解法一数组加双指针先保住正确性再谈优化我的刷题习惯是第一个 AC 的版本不需要追求最优先让思路跑通。数组解法是最贴近直觉的也最容易写对。放到面试里它反而是很好的表达起点。2.1 为什么暴力解法反而是很多面试里安全的开场很多人觉得面试写暴力解法会被面试官扣分我不同意。面试官更在意的是你能不能从暴力解法出发一步步推导到最优解。你先写出数组解法等于展示了你懂得拆问题然后你再主动说一句数组的空间复杂度还能优化可以用快慢指针做到 O(1)这才是完整的答题链条。反过来一上来就写快慢加反转如果中点条件写错一个整个思路当场翻车反而不划算。还有一个现实原因LeetCode 的很多测试用例链长就是几百个节点数组解法完全能跑过。真正限制你的是面试时的表达不是 O(n) 空间的常数级占用。我把数组解法放在前面不是因为它最好而是因为它最稳。2.2 数组解法的代码实现与复杂度分析核心逻辑三步遍历链表收集值、双指针从两端夹逼、遇到不等就返回 False。from typing import Optional class ListNode: def __init__(self, val0, nextNone): self.val val self.next next 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)。这里必须强调一点收集进数组的是 val 值不是节点对象。节点对象之间的比较往往没有意义因为两段链表里值相同的节点十有八九是不同对象按对象比较会直接误判。2.3 数组解法里容易被忽略的边界第一个边界是空链表和单节点链表。空链表和只有一个节点的链表按定义都算回文。数组解法天然能处理因为空数组和只有一个元素的数组进入双指针循环后不会触发不相等判断直接返回 True。第二个边界是节点值不一定是整数。如果 val 是字符串或者浮点数比较逻辑要保证两边元素类型一致。绝大多数题目给的都是整数知道这个坑就行。第三个细节我见很多人踩过把 ListNode 对象本身 append 进数组然后写list[left] list[right]。在 Python 里如果 ListNode 没有重写__eq__默认比较的是对象内存地址于是两个 val 相同但 next 指向不同的节点会被判定为不相等结果连 1-2-2-1 这种标准回文都过不了。所以务必收集 val这是数组解法最容易翻车的地方。3. 解法二快慢指针找中点反转后半段O(1)空间的经典组合拳数组解法的空间瓶颈在于复制了一整条链表。要省掉这份空间唯一的路就是原地操作。思路可以拆成四步找中点、反转后半段、同时遍历比较、按需恢复链表。每一步我都会把最容易写错的地方讲透。3.1 找中点快慢指针的循环条件决定奇偶对齐找中点用的是双指针slow 每次走一步fast 每次走两步等 fast 走不动时slow 大概停在中间。但这个大概里藏着整道题最大的坑偶数长度的链表中点到底算左边那个还是右边那个我推荐统一使用while fast.next and fast.next.next:让 slow 停在左中点偶数长度或者正中间节点奇数长度。用几个例子可以看得很清楚链表长度slow 最终位置后半段起点2第 1 个节点第 2 个节点3第 2 个节点中间第 3 个节点4第 2 个节点左中点第 3 个节点5第 3 个节点中间第 4 个节点为什么不用常见的while fast and fast.next:因为这种写法会让 slow 停在偶数长度的右中点。右中点也能做但后半段从 slow.next 开始时前半段和后半段的长度会出现偏差你得额外处理中间节点是否参与比较的问题容易把自己绕晕。左中点写法最干净后半段固定从 slow.next 开始前半段从 head 走到 slow 结束边界清清楚楚。3.2 反转后半段逐节点比较找完中点之后后半段起点是 slow.next。接下来把这一小段链表反转。反转链表是另一道经典题核心就是三行指针交换def reverseList(self, head): prev None cur head while cur: nxt cur.next cur.next prev prev cur cur nxt return prev反转之后后半段原来在末尾的节点变成了新链表的头。这里有一个我很想强调的细节我并没用slow.next None去截断链表。反转从 slow.next 开始的部分不会影响 slow 之前的节点所以不截断也安全。比较阶段里first 从 head 走second_half 从反转后的头走当 second_half 走到空时first 正好停在左中点或中间节点两边比较次数完全对齐。完整代码如下我把可选的恢复步骤也放进去了from typing import Optional class Solution: def isPalindrome(self, head: Optional[ListNode]) - bool: if not head or not head.next: return True # 1. 快慢指针找左中点 slow, fast head, head while fast.next and fast.next.next: slow slow.next fast fast.next.next # 2. 反转后半段 second self.reverseList(slow.next) # 3. 比较前半段与反转后的后半段 first, second_half head, second result True while second_half: if first.val ! second_half.val: result False break first first.next second_half second_half.next # 4. 恢复链表不影响判断结果 slow.next self.reverseList(second) return result def reverseList(self, head: Optional[ListNode]) - Optional[ListNode]: prev None cur head while cur: nxt cur.next cur.next prev prev cur cur nxt return prev时间 O(n)空间 O(1)。如果不需要恢复链表可以直接去掉第 4 步在比较循环结束后返回 result。但要注意如果比较中发现不相等走到 break最后也还是要走恢复逻辑不能直接 return False否则链表就停在半路被改写过的状态。3.3 恢复链表到底是不是必须的先给结论做题可以不要恢复面试建议保留恢复。不恢复的理由很实在函数返回之后外部程序一般不会再读取这条链表的 next 指向判题系统也不检查链表是否保持原状。但面试里面试官如果追问你的解法会不会修改输入数据你能主动说出可以在比较完之后把后半段再反转回来恢复原链表结构这是很加分的细节。恢复的写法是slow.next self.reverseList(second)。这里的 second 是反转后的后半段头对它再反转一次得到的是原始后半段的头把它重新挂到 slow.next 上就可以了。关键点是必须用 result 变量保存比较结果恢复完成后再统一返回否则提前 return 会跳过恢复。真实项目里我强烈建议保留恢复逻辑。很多业务场景中传入的链表可能还被别的地方引用你贸然改掉它的结构容易引发难以排查的副作用。4. 边界条件与典型错误排查把这些坑填平面试才能稳回文链表的代码一旦写错多半不是思路问题而是边界问题。我把自己踩过、也帮别人排查过的错误整理成几类你看完应该能省下不少调试时间。4.1 最容易翻车的四种链表形态第一空链表和单节点链表。单节点一定满足回文定义空链表按定义也返回 True。我在代码开头直接写if not head or not head.next: return True一步挡住后面所有边界问题。第二偶数长度回文比如 1-2-2-1。这里要验证 slow 停在第一个 2 而不是第二个 2。用左中点写法slow 停在第一个 2后半段反转前是 2-1反转后是 1-2。比较时 first 依次取 1、2second_half 依次取 1、2完美对齐。第三奇数长度回文比如 1-2-3-2-1。slow 停在 3后半段反转前是 2-1反转后是 1-2。循环只比较两次1 对 1、2 对 2中间节点 3 完全不需要参与因为回文定义里中间元素自身天然对称。第四链表所有值都相同。这种情况不需要特殊处理比较逻辑仍然逐节点走不会因为值重复就跳过判断。比如 1-1-2-1-1真正比较时会发现两头不对称正常返回 False。4.2 快慢指针写错导致的错位和空指针最常见的错位是循环条件写成while fast and fast.next:。在这种写法下偶数长度链表的 slow 会停在右中点后半段从 slow.next 开始时会少一个节点结果就是漏比较。这种 bug 不是每个测试用例都会触发往往只有偶数长度用例才会露馅非常难定位。另一个高频错误是空指针异常。有人会把 fast 初始化为 head.next在单节点或者两节点链表上循环里一写 fast.next 就会访问 None 的属性。稳妥做法是 fast 也从头开始循环条件用fast.next and fast.next.next做两重保护天然不会越界。还有一个细节反转后半段前不需要手动把 slow.next 置空。有人习惯性写slow.next None想隔断两段结果后半段已经拿不到了除非先保存引用。我的模板里不断开reverseList(slow.next) 拿到的是后半段头反转过程也不会影响 slow 之前的部分安全性更高。4.3 常见错误速查表故障现象可能原因修正方法偶数长度回文被判 Falsefast 循环条件用了while fast and fast.next换成while fast.next and fast.next.next单节点链表抛空指针fast 初始化为 head.next让 fast 从头开始或开头直接判单节点返回反转后半段后链表成环reverseList 里漏掉 nxt 保存每个 cur 反转前先记下 cur.next全部值相同但结果误判比较的是节点对象而不是 val使用 first.val second_half.val提前 return 导致链表没恢复中途 break 后直接返回用 result 变量保存结果恢复后再返回还有一个很隐蔽的细节如果你在比较循环里直接写return False那么恢复链表永远不会有执行机会。我见过很多人第一次加恢复逻辑时False 分支直接 return恢复代码成了摆设。统一用 result 变量后逻辑会清楚很多。5. 从这道题延伸出来的实战心得刷题越到后面越能体会套路积累的价值。回文链表本身不难但它把两个高频套路绑定在一起价值就上了一个台阶。5.1 面试怎么把 O(1) 空间方案讲清楚面试里聊这道题我建议按从暴力到最优的顺序讲不要一上来就甩快慢指针答案。你可以先说直观做法是复制数组双指针判断空间 O(n)然后主动提如果要求不额外用空间可以找到中点反转后半段再从两头同时比较空间 O(1)最后补一句比较完可以把后半段反转回来不改动原链表。讲到快慢指针找中点时重点向面试官解释奇偶处理。你可以说我采用左中点策略后半段固定从 slow.next 开始这样比较次数是 n//2不需要单独判断中间节点。如果面试官追问为什么不用while fast and fast.next就回答这类写法停在右中点偶数长度需要额外修正不够干净。我自己的感受是这个回答顺序既展示了暴力解又展示了优化意识还能体现对边界条件的敏感综合印象分比闷头写代码高很多。5.2 把这道题串成一条链表学习线回文链表其实站在两道更基础的题肩上快慢指针找中点和反转链表。如果你发现自己在本题卡住多半是这两块单独还不够熟。我建议先做链表的中间结点这道题把找中点练熟再做反转链表做到手写不卡壳最后回到本题整套组合就顺畅了。类似的题目还有回文数、验证回文串它们不是链表题但检测回文的双指针思路完全相同。数组题和链表题在回文主题上是互通的多刷几道之后会越来越有感觉。至于如果链表有环还能不能用这套解法那是扩展题需要先判环否则找中点会陷入死循环。5.3 给刷 Hot100 的同学一个实操建议如果你按主题刷到这道题我建议至少用两种方式各写一遍。第一遍用数组解法把正确性跑通不要觉得写暴力就不好意思第二遍用快慢加反转最好能默写。默写时重点检查三处循环条件是fast.next and fast.next.next还是fast and fast.next反转链表的三个指针交换顺序对不对比较阶段要不要恢复链表。我个人做这道题最大的收获不是背会了模板而是真正把找中点和反转链表两个独立套路拼装成了一台机器。后来遇到需要拆链表、合并链表的题目思维顺畅了很多。如果你卡在这里吃力不妨先把那两道前置题单独练熟再回来看本文第 3 节。链表题的 bug有一大半出在游离的 next 指针上一个节点被访问后旧 next 没保存新 next 没接对整个结构就乱了。回文链表恰好把这类问题浓缩在一起所以它值得反复写。写熟之后对后面刷合并有序链表、反转区间、判断环形链表都有直接的帮助。

回文链表怎么判断？快慢指针加反转链表，O(1)空间搞定 LeetCode 234

相关推荐

基于Django的评论热点挖掘与情感分析系统实践

VS2019下Ceres预编译库配置：lib/dll挂接与避坑指南

移动端UI自动化新范式：AOM框架原理、迁移实践与实测对比

更多资讯

sqlmap实战：自动化检测DVWA靶场SQL注入漏洞

AI Agent沙箱：生产级意图执行隔离与安全运行时架构

Arthas实战：从CPU飙高到秒定位线上Java问题，十分钟救火指南

机械生学C语言入门：从开发环境到变量输入输出

DFMEA实战：热分析仪器温度链路失效分析与风险控制要点

个人AI助手的语义感知缓存系统设计与实现

今日更新

电商智能运营体系从0到1：架构设计、落地步骤与避坑指南

压缩空气储能与热网热惯性联合优化调度：热电联产系统建模与求解

若依框架AI代码生成不稳定？用Agent Skill三层结构+五步法搞定

本周精选

金融AI落地指南：从调研报告到技术选型与工程实践

大模型上下文成本与注意力优化技术深度解析——为何O(n²)平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测

基于GMM的语音识别系统原理与MATLAB实现详解

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？