LeetCode第234题“回文链表”我最早是在刷Hot 100的时候碰到的后来面试也被问过两三次可以说是链表题目里出镜率特别高的一道基础题。题目本身不难但想写出能过、能讲、能扩展到其他题的解法还真不是看一眼答案就完事的事。尤其是“快慢指针找中点”和“反转后半段”这套组合拳很多新手一开始只是背代码没搞明白为什么这么写等到面试被追问一句“奇数长度你怎么处理”就卡壳了。这篇文章我是按自己的刷题复盘思路整理的先讲清楚题目在考什么再把最优解的每个步骤拆到能讲给面试官听最后附上我踩过的坑和自查方法。适合刚刷完链表基础、想彻底吃透双指针与原地操作的朋友。1. 题目确认与最优解选择1.1 回文链表到底在考什么先对齐一下题目输入输出给你单链表的头节点 head判断这个链表是否为回文链表。回文的意思就是从前往后读和从后往前读结果一样比如1 - 2 - 3 - 2 - 1就是回文1 - 2 - 2 - 1也是而1 - 2 - 3不是。这里每个节点的 val 是整数链表长度最少为 0最多到 10 的 5 次方级别所以题目要求你在 O(n) 时间范围内解决问题。为什么链表判回文比数组麻烦因为数组可以用两个下标一个从左往右、一个从右往左夹逼着比较。但单链表只有 next 指针你从 head 出发永远往后走没法直接“从尾巴往前读”。所以做这道题通常要绕两步第一步想办法把后半段链表拿到手第二步把后半段倒过来和前半段比。这其实在考三个基本功快慢指针找中间节点、单链表反转、以及边界条件下如何不出错。另外提醒一句题目默认允许修改链表LeetCode 判题时不会检查你是否把链表恢复原样。但真实面试里面试官有可能会追问“如果要求不修改原链表结构你怎么办”这一点我在章节 4 里会单独说。1.2 为什么首选快慢指针加反转而不是转数组我第一次做这道题时第一反应就是“转成数组再判断”。思路非常直白遍历链表把每个节点的值放进列表然后左右指针往中间扫。伪代码写出来就是nums [] while head: nums.append(head.val) head head.next left, right 0, len(nums) - 1 while left right: if nums[left] ! nums[right]: return False left 1 right - 1 return True这个解法能过而且代码量很少。但你看一下空间复杂度额外开了一个长度 n 的数组所以是 O(n) 空间。LeetCode 对这道题没有强制空间限制可面试官看到你上来就转数组大概率会追问“能不能 O(1) 空间解决”。原因也很简单如果这个链表大到几百 MB你还要再开一份同样的内存去存拷贝显然不优雅。真正的 O(1) 空间思路就是利用链表本身的结构来“制造”一个从中间往后倒序走的后半段。你得先找到中间位置然后把后半段原地反转反转之后再从 head 出发和反转后的头节点一起往后比。这样除了几个指针变量不申请额外容器空间复杂度是 O(1)。时间复杂度依然是 O(n)因为快慢指针遍历一次 n/2反转再遍历 n/2最后比较 n/2总次数 n 的常数倍这就是面试官最想看到的方案。所以结论很明确转数组适合快速验证思路适合笔试里赶时间但如果目标是面试、是想理解链表操作的底层逻辑那就必须掌握快慢指针加反转。这篇文章后面的所有内容也都围绕这个最优解展开。2. 核心原理找中间节点与反转链表2.1 快慢指针如何精确地找到中点快慢指针找中点的核心很简单两个指针同时从 head 出发慢指针每次走一步快指针每次走两步。当快指针走到链表末尾或者越过末尾时慢指针恰好停在中间位置附近。我见过很多新手死记口诀“慢走一步快走两步”但没搞懂为什么结果一遇到奇数长度和偶数长度就写错。这里有一个特别容易混淆的细节常见的循环条件是while fast and fast.next:在这个条件下奇数长度链表循环结束后slow 会停在正中间偶数长度链表循环结束后fast 变成 nullslow 会停在“右中位”也就是中间靠右的那个节点。举个例子1 - 2 - 3 - 2 - 1循环结束后 fast 指向最后一个节点 1slow 指向 3。1 - 2 - 2 - 1循环结束后 fast 是 nullslow 指向第二个 2也就是靠右的那个 2。这就产生一个问题如果我们想比较左半段和右半段直接反转 slow 后面的节点可能不够。比如偶数长度的1 - 2 - 2 - 1slow 停在第二个 2 上如果反转slow.next那后半段只剩一个 1根本没法完整比较。所以处理后必须补一步如果循环结束时 fast 不是 null说明总长度是奇数slow 需要再往后挪一位让 slow 指向右半段的真正起点。官方题解里通常写if fast: slow slow.next也就是说奇数长度时抛掉最中间那个不需要参与比较的节点slow 直接从中间节点的下一个开始。偶数长度时 fast 为 nullslow 已经停在右半段起点什么都不用做。这一步是整个代码里最容易漏的也是面试官最爱追问的点。如果你觉得这个 if 不太好记也可以用另一种初始化方式让 fast 从head.next出发慢指针从 head 出发。这样循环结束后slow 停在左中位slow.next就是右半段起点无论奇偶都一致。这种写法逻辑更统一但很多同学会搞混快慢指针的初始值所以我个人更推荐官方那套“先找中点奇数值再补一步”一步一步说出来反而更容易让对方听懂。2.2 链表反转的迭代实现与记忆技巧单链表反转是一个必须形成肌肉记忆的基础操作。迭代写法只有四步prev None cur slow while cur: nxt cur.next cur.next prev prev cur cur nxt每次循环里先用 nxt 提前保存当前节点的下一个节点这是最关键的一步。因为当你把cur.next指向前一个节点后原来的下一个节点就断了没有提前保存的话链表后半截就找不回来了。你可以把反转理解成“拆链子再反方向串起来”prev 始终是已经反转好的那一段链子的头cur 是还没处理的原链表头部nxt 是下一颗还没拆的珠子。反转结束后prev 就是反转后新链表的头节点。在我们这道题里反转后半段之后prev 就指向了从后往前读的后半段开头。这里有个容易晕的地方原链表后半段是slow - slow.next - ... - tail反转之后变成tail - ... - slow.next - slow但你不是从原来的 tail 去遍历而是通过 prev 这个新头节点去遍历。只要记住“prev 是新的 head”就不会乱。如果时间充裕建议顺手把链表反转的实现也写成递归版本便于理解链表递归思路def reverse(head): if not head or not head.next: return head new_head reverse(head.next) head.next.next head head.next None return new_head但实际操作里迭代版本能避免递归深度问题也不会因为栈溢出被面试官质疑。所以这道题我们全部用迭代实现。3. 完整题解代码与逐段拆解Python3.1 可提交的完整代码下面这段 Python 代码是我在实际提交时用的版本可以直接粘到 LeetCode 里跑。这里有一点要先说明我为了让代码可读性更好把“找中点”“反转链表”拆成了两段注释但面试时你也可以把它们封装成两个独立函数看个人习惯。class Solution: def isPalindrome(self, head: Optional[ListNode]) - bool: # 1. 快慢指针找中点 slow head fast head while fast and fast.next: slow slow.next fast fast.next.next # 2. 奇数长度时跳过正中间的节点 if fast: slow slow.next # 3. 反转后半段链表 prev None cur slow while cur: nxt cur.next cur.next prev prev cur cur nxt # 4. 前半段和反转后的后半段逐节点比较 left head right prev while right: if left.val ! right.val: return False left left.next right right.next return True跑一遍用例心里就有数了。输入head [1,2,2,1]快慢指针结束时 slow 停在第二个 2fast 为 null不需要额外调整反转 slow 开始的后半段得到1 - 2 - 2注意原来的顺序是 2 - 1反转后变成 1 - 2然后用 left 从原头部 1 开始right 从反转后的头部 1 开始依次比较1 对 1、2 对 2最后返回 True。输入head [1,2,3,2,1]slow 停在中间的 3fast 非 null所以 slow 再走一步指向第二个 2反转后得到1 - 2left 从 1 开始比较 1 对 1、2 对 2中间的 3 被自然跳过返回 True。3.2 关键步骤的调试级解释我重点解释两个最容易出问题的位置。第一个是“找中点时快慢指针的终止条件”。很多初学者会写while fast.next and fast.next.next这在某些长度下也能跑但奇数长度时 fast 会停在倒数第二个节点slow 不落在预期位置处理起来更绕。官方解法最常见的是while fast and fast.next理由是快指针每轮移动两步它既要确保当前节点非空也要确保下一跳非空。如果 fast 已经走到最后一个节点它不建议因为 fast 不能跳两步。这时循环结束slow 停在正中间。反之如果 fast 变成了 null说明链表长度是偶数slow 停在中间偏右的位置。第二个是“为什么比较循环用 while right而不是 while left”。因为反转后的后半段长度在奇数情况下比前半段少一个节点中间节点被跳过了假如你写while left当 right 已经走到 nullleft 可能还剩下一个中间节点代码会尝试访问right.val直接报空指针异常。用while right就非常安全逻辑上也说得通只要两个链表要比较的节点都还有值就比较后半段先走完说明比较完毕返回 True。另外有的同学喜欢在比较时同时把原链表恢复比如在返回前把后半段再反转一次。这不算错只是 LeetCode 不需要。恢复的好处是面试里展示你考虑了副作用坏处是代码变长、容易写错。我自己的建议是提交答案不恢复面试时口头提一句“如果面试环境要求不修改原链表我会先把后半段恢复回去”就够了。4. 边界条件与常见错误速查4.1 空链表、单节点、奇偶长度的处理边界条件往往是面试题里真正拉开差距的地方。这道题最常见的三个边界是全空、单节点、两个节点。空链表head 为 null。按上面的代码slow 和 fast 都是 null进入不了 while 循环fast 是 null不会执行 if fast 分支反转后半段时 prev 也还是 null比较循环 while right 直接不执行返回 True。数学上空链表被认为是回文LeetCode 测试用例也这么认为所以代码天然支持不用额外写 if。单节点head 只有一个节点。while 循环同样不执行fast 不是 null所以 slow 走一步到 null反转 null 之后 prev 还是 null比较循环不执行返回 True。单个节点当然是回文。两个节点比如1 - 2。快慢指针走一轮slow 指向 2fast 变成 nullfast 为 null不补位反转 slow 开始的后半段就是反转节点 2 本身prev 指向 2比较left 为 1right 为 2值不相等返回 False。正确。再比如1 - 1比较时值相等left 和 right 都变成 null循环结束返回 True也正确。还有一个我在实际提交中遇到过的情况节点值可能是负数。比如[-129, -129]回文判断只比较 val 是否相等不涉及大小比较所以负数一样能跑。你只要别看到负数就觉得是无效输入就行。4.2 面试时需要留意的点面试的时候不要上来就写代码最好先按这个顺序跟面试官对齐先问清楚“可不可以修改输入的链表”。绝大多数情况下 LeetCode 允许但面试场景里有的面试官会故意设限。如果不能修改链表结构那 O(1) 空间的思路就失效了你需要用递归或者显式栈来从后往前访问链表空间复杂度升到 O(n)到时候要主动说明权衡。讲思路时一定要提奇数长度处理。我自己面试时说的原话是“快慢指针停在中间如果 fast 不为空说明是奇数长度中间节点不用比我让 slow 挪到右半段起点。”这句话基本是整道题的高光点多说一句面试官就知道你是真懂而不是背题。代码别写得过于花哨。有的同学喜欢把链表反转写成内部函数再调用个人不太推荐在紧张状态下引入过多函数栈。直接在 isPalindrome 里按顺序写完反而更清晰。如果面试官要求模块化再现场拆成辅助函数也不迟。5. 实战复盘从暴力解到 O(1) 空间的演进5.1 为什么转数组不是最优转数组方案代码确实简洁但它有三个隐藏问题一是额外空间 O(n)对大链表不友好二是它没有锻炼到链表操作能力换个变种题就抓瞎三是如果面试官接着问“如果链表很长放不进数组怎么办”你没法答。我之前还真在面试里被追问过这个。当时我先说了转数组解法面试官点头然后问我能不能优化空间。如果我只会背答案肯定接不住。所以后来我刷这道题时会刻意要求自己第一遍先用最直觉的方法写出来第二遍再强迫自己用 O(1) 空间重写两版代码放一起对比。这个方法对准备面试非常有效。需要说明的是转数组和快慢指针加反转都是正确的没有绝对好坏只有“在某个约束条件下更合适”。如果题目明确只求快速通过或者面试官说不管空间那转数组反而更省事。但作为经典题理解最优解仍然是必须的。5.2 递归方案的价值与局限链表回文还有一种递归做法维护一个外部指针 p递归访问到链表尾部然后在回溯过程中不断把 p 往右移和当前递归访问到的节点值比较核心逻辑大概是def check(head): nonlocal p if not head: return True if not check(head.next): return False if p.val ! head.val: return False p p.next return True这个方案思路很优雅天然实现了“一个指针从头往尾走一个指针从尾往头走”的效果。但它有两个明显局限第一递归深度等于链表长度链表长度到 10 万级别时Python 默认递归深度会报错C 和 Java 也存在栈溢出风险第二严格来说它借助了调用栈空间复杂度是 O(n)并不满足最优解要求。所以我觉得递归更适合作为理解链表回溯的思维实验不适合作为这道题的最终提交方案。面试时如果提到递归你可以这样收尾“递归思路能帮助理解但实际工程里我更倾向迭代避免栈溢出。”这句话显得你既有理论能力又有工程判断力。5.3 这道题在热门 100 题里的定位回文链表被收录在 LeetCode 热门 100 题Hot 100和经典题单里并不是偶然。它不像难题那样考高深算法而是把“找中点”“反转链表”“双指针比较”三个高频操作一次性串起来。这三板斧在链表题里几乎无处不在找中点是876. 链表的中间结点反转链表是206. 反转链表而回文链表就是它们的合体版。周赛里也经常能看到它的变体。可能不是直接叫“回文链表”而是换一个壳子比如“判断链表是否对称”“删除链表中最短回文子串”“在链表上做回文扩展”等等。热词里提到的周赛 430 虽然和这道题没有直接关系但你在周赛复盘时会发现很多链表题只要提取出“中点”和“反转”两个动作思路就会清晰很多。所以我的建议是这道题刷完之后不要四处找偏题怪题先把它的两个组件题各刷两遍再用回文链表做组合练习。这个组合套路一旦形成肌肉记忆你在后续刷其他链表题时会明显感觉顺畅很多。6. 常见问题与排查技巧实录6.1 本地测试通过但提交超时的原因超时多半不是因为算法复杂度而是因为代码里有死循环。回文链表这道题里最常见的死循环是反转链表时没有正确维护 nxt 指针。比如有的人会写成while cur: cur.next prev prev cur cur cur.next看起来没问题但仔细看第三步你在第二步已经改了 cur.next此时cur cur.next取的其实是更新后的 next也就是 prev于是 cur 又指回已经处理过的节点链表形成环循环永远出不去。调试时很容易发现程序卡住但新手经常盯着 while 条件看半天没意识到是 cur 步进错了。正确的写法是先保存原 next再改指针最后用保存的 nxt 步进。也就是本文前面写的那个三行顺序。我记得自己刚学的时候几乎每隔一周就会写错一次这一步后来索性总结成一句话“先存后改”就再也没错过了。还有一个隐蔽的问题是快慢指针找中点时fast 的判空顺序。如果你写成while fast.next and fast:当 fast 是 null 时会先访问fast.next直接抛空指针异常而不是返回正常结果。所以判空一定要把fast写在前fast.next写在后。6.2 如何用最小测试集自查我刷题的习惯是提交之前先在脑袋里或者本地跑几个最小用例不用多5 个就够覆盖主要分支[]空链表预期 true。[1]单节点预期 true。[1, 2]两个不同值预期 false。[1, 2, 2, 1]偶数长度回文预期 true。[1, 2, 3, 2, 1]奇数长度回文预期 true。再加一个特殊的[1, 2, 3, 1]这种不是回文的奇数长度预期 false。这 6 个用例跑完基本能把空指针、奇偶判断、比较退出条件全部覆盖到。如果本地跑某个用例失败先定位在哪一步。我建议在找完中点后打印 slow.val在反转完成后打印 prev 的链表这样能快速知道是中点找错还是反转写错。不要一上来就怀疑某个很远的环节链表题 90% 的问题都出在那几根指针的赋值顺序上。6.3 一点个人心得这道题我在一年多里反复写过不下十次每次写都有新的体会。最早是背答案后来是理解“奇数长度要跳过中间节点”再后来才意识到while right这个终止条件背后还藏着“后半段更短”这一层。最近一次写的时候我又问自己“如果不修改链表结构用读写不破坏原链表的方式能不能也做到 O(1)”答案是不行因为从本质上讲单链表要反向访问只能借助额外存储。能把这道题从“会写”讲到“为什么”就是我眼中真正刷透的状态。所以最后想分享的小技巧是如果面试时间充裕你可以在代码末尾主动提出“要不要我恢复链表结构”这通常是加分项。因为面试官看到的不只是你会解这道题还能看到你考虑副作用、具备基本工程素养。这篇复盘就是我目前对回文链表最完整的一份记录希望对你也有参考价值。
回文链表最优解：快慢指针找中点与反转链表全解析
LeetCode第234题“回文链表”我最早是在刷Hot 100的时候碰到的后来面试也被问过两三次可以说是链表题目里出镜率特别高的一道基础题。题目本身不难但想写出能过、能讲、能扩展到其他题的解法还真不是看一眼答案就完事的事。尤其是“快慢指针找中点”和“反转后半段”这套组合拳很多新手一开始只是背代码没搞明白为什么这么写等到面试被追问一句“奇数长度你怎么处理”就卡壳了。这篇文章我是按自己的刷题复盘思路整理的先讲清楚题目在考什么再把最优解的每个步骤拆到能讲给面试官听最后附上我踩过的坑和自查方法。适合刚刷完链表基础、想彻底吃透双指针与原地操作的朋友。1. 题目确认与最优解选择1.1 回文链表到底在考什么先对齐一下题目输入输出给你单链表的头节点 head判断这个链表是否为回文链表。回文的意思就是从前往后读和从后往前读结果一样比如1 - 2 - 3 - 2 - 1就是回文1 - 2 - 2 - 1也是而1 - 2 - 3不是。这里每个节点的 val 是整数链表长度最少为 0最多到 10 的 5 次方级别所以题目要求你在 O(n) 时间范围内解决问题。为什么链表判回文比数组麻烦因为数组可以用两个下标一个从左往右、一个从右往左夹逼着比较。但单链表只有 next 指针你从 head 出发永远往后走没法直接“从尾巴往前读”。所以做这道题通常要绕两步第一步想办法把后半段链表拿到手第二步把后半段倒过来和前半段比。这其实在考三个基本功快慢指针找中间节点、单链表反转、以及边界条件下如何不出错。另外提醒一句题目默认允许修改链表LeetCode 判题时不会检查你是否把链表恢复原样。但真实面试里面试官有可能会追问“如果要求不修改原链表结构你怎么办”这一点我在章节 4 里会单独说。1.2 为什么首选快慢指针加反转而不是转数组我第一次做这道题时第一反应就是“转成数组再判断”。思路非常直白遍历链表把每个节点的值放进列表然后左右指针往中间扫。伪代码写出来就是nums [] while head: nums.append(head.val) head head.next left, right 0, len(nums) - 1 while left right: if nums[left] ! nums[right]: return False left 1 right - 1 return True这个解法能过而且代码量很少。但你看一下空间复杂度额外开了一个长度 n 的数组所以是 O(n) 空间。LeetCode 对这道题没有强制空间限制可面试官看到你上来就转数组大概率会追问“能不能 O(1) 空间解决”。原因也很简单如果这个链表大到几百 MB你还要再开一份同样的内存去存拷贝显然不优雅。真正的 O(1) 空间思路就是利用链表本身的结构来“制造”一个从中间往后倒序走的后半段。你得先找到中间位置然后把后半段原地反转反转之后再从 head 出发和反转后的头节点一起往后比。这样除了几个指针变量不申请额外容器空间复杂度是 O(1)。时间复杂度依然是 O(n)因为快慢指针遍历一次 n/2反转再遍历 n/2最后比较 n/2总次数 n 的常数倍这就是面试官最想看到的方案。所以结论很明确转数组适合快速验证思路适合笔试里赶时间但如果目标是面试、是想理解链表操作的底层逻辑那就必须掌握快慢指针加反转。这篇文章后面的所有内容也都围绕这个最优解展开。2. 核心原理找中间节点与反转链表2.1 快慢指针如何精确地找到中点快慢指针找中点的核心很简单两个指针同时从 head 出发慢指针每次走一步快指针每次走两步。当快指针走到链表末尾或者越过末尾时慢指针恰好停在中间位置附近。我见过很多新手死记口诀“慢走一步快走两步”但没搞懂为什么结果一遇到奇数长度和偶数长度就写错。这里有一个特别容易混淆的细节常见的循环条件是while fast and fast.next:在这个条件下奇数长度链表循环结束后slow 会停在正中间偶数长度链表循环结束后fast 变成 nullslow 会停在“右中位”也就是中间靠右的那个节点。举个例子1 - 2 - 3 - 2 - 1循环结束后 fast 指向最后一个节点 1slow 指向 3。1 - 2 - 2 - 1循环结束后 fast 是 nullslow 指向第二个 2也就是靠右的那个 2。这就产生一个问题如果我们想比较左半段和右半段直接反转 slow 后面的节点可能不够。比如偶数长度的1 - 2 - 2 - 1slow 停在第二个 2 上如果反转slow.next那后半段只剩一个 1根本没法完整比较。所以处理后必须补一步如果循环结束时 fast 不是 null说明总长度是奇数slow 需要再往后挪一位让 slow 指向右半段的真正起点。官方题解里通常写if fast: slow slow.next也就是说奇数长度时抛掉最中间那个不需要参与比较的节点slow 直接从中间节点的下一个开始。偶数长度时 fast 为 nullslow 已经停在右半段起点什么都不用做。这一步是整个代码里最容易漏的也是面试官最爱追问的点。如果你觉得这个 if 不太好记也可以用另一种初始化方式让 fast 从head.next出发慢指针从 head 出发。这样循环结束后slow 停在左中位slow.next就是右半段起点无论奇偶都一致。这种写法逻辑更统一但很多同学会搞混快慢指针的初始值所以我个人更推荐官方那套“先找中点奇数值再补一步”一步一步说出来反而更容易让对方听懂。2.2 链表反转的迭代实现与记忆技巧单链表反转是一个必须形成肌肉记忆的基础操作。迭代写法只有四步prev None cur slow while cur: nxt cur.next cur.next prev prev cur cur nxt每次循环里先用 nxt 提前保存当前节点的下一个节点这是最关键的一步。因为当你把cur.next指向前一个节点后原来的下一个节点就断了没有提前保存的话链表后半截就找不回来了。你可以把反转理解成“拆链子再反方向串起来”prev 始终是已经反转好的那一段链子的头cur 是还没处理的原链表头部nxt 是下一颗还没拆的珠子。反转结束后prev 就是反转后新链表的头节点。在我们这道题里反转后半段之后prev 就指向了从后往前读的后半段开头。这里有个容易晕的地方原链表后半段是slow - slow.next - ... - tail反转之后变成tail - ... - slow.next - slow但你不是从原来的 tail 去遍历而是通过 prev 这个新头节点去遍历。只要记住“prev 是新的 head”就不会乱。如果时间充裕建议顺手把链表反转的实现也写成递归版本便于理解链表递归思路def reverse(head): if not head or not head.next: return head new_head reverse(head.next) head.next.next head head.next None return new_head但实际操作里迭代版本能避免递归深度问题也不会因为栈溢出被面试官质疑。所以这道题我们全部用迭代实现。3. 完整题解代码与逐段拆解Python3.1 可提交的完整代码下面这段 Python 代码是我在实际提交时用的版本可以直接粘到 LeetCode 里跑。这里有一点要先说明我为了让代码可读性更好把“找中点”“反转链表”拆成了两段注释但面试时你也可以把它们封装成两个独立函数看个人习惯。class Solution: def isPalindrome(self, head: Optional[ListNode]) - bool: # 1. 快慢指针找中点 slow head fast head while fast and fast.next: slow slow.next fast fast.next.next # 2. 奇数长度时跳过正中间的节点 if fast: slow slow.next # 3. 反转后半段链表 prev None cur slow while cur: nxt cur.next cur.next prev prev cur cur nxt # 4. 前半段和反转后的后半段逐节点比较 left head right prev while right: if left.val ! right.val: return False left left.next right right.next return True跑一遍用例心里就有数了。输入head [1,2,2,1]快慢指针结束时 slow 停在第二个 2fast 为 null不需要额外调整反转 slow 开始的后半段得到1 - 2 - 2注意原来的顺序是 2 - 1反转后变成 1 - 2然后用 left 从原头部 1 开始right 从反转后的头部 1 开始依次比较1 对 1、2 对 2最后返回 True。输入head [1,2,3,2,1]slow 停在中间的 3fast 非 null所以 slow 再走一步指向第二个 2反转后得到1 - 2left 从 1 开始比较 1 对 1、2 对 2中间的 3 被自然跳过返回 True。3.2 关键步骤的调试级解释我重点解释两个最容易出问题的位置。第一个是“找中点时快慢指针的终止条件”。很多初学者会写while fast.next and fast.next.next这在某些长度下也能跑但奇数长度时 fast 会停在倒数第二个节点slow 不落在预期位置处理起来更绕。官方解法最常见的是while fast and fast.next理由是快指针每轮移动两步它既要确保当前节点非空也要确保下一跳非空。如果 fast 已经走到最后一个节点它不建议因为 fast 不能跳两步。这时循环结束slow 停在正中间。反之如果 fast 变成了 null说明链表长度是偶数slow 停在中间偏右的位置。第二个是“为什么比较循环用 while right而不是 while left”。因为反转后的后半段长度在奇数情况下比前半段少一个节点中间节点被跳过了假如你写while left当 right 已经走到 nullleft 可能还剩下一个中间节点代码会尝试访问right.val直接报空指针异常。用while right就非常安全逻辑上也说得通只要两个链表要比较的节点都还有值就比较后半段先走完说明比较完毕返回 True。另外有的同学喜欢在比较时同时把原链表恢复比如在返回前把后半段再反转一次。这不算错只是 LeetCode 不需要。恢复的好处是面试里展示你考虑了副作用坏处是代码变长、容易写错。我自己的建议是提交答案不恢复面试时口头提一句“如果面试环境要求不修改原链表我会先把后半段恢复回去”就够了。4. 边界条件与常见错误速查4.1 空链表、单节点、奇偶长度的处理边界条件往往是面试题里真正拉开差距的地方。这道题最常见的三个边界是全空、单节点、两个节点。空链表head 为 null。按上面的代码slow 和 fast 都是 null进入不了 while 循环fast 是 null不会执行 if fast 分支反转后半段时 prev 也还是 null比较循环 while right 直接不执行返回 True。数学上空链表被认为是回文LeetCode 测试用例也这么认为所以代码天然支持不用额外写 if。单节点head 只有一个节点。while 循环同样不执行fast 不是 null所以 slow 走一步到 null反转 null 之后 prev 还是 null比较循环不执行返回 True。单个节点当然是回文。两个节点比如1 - 2。快慢指针走一轮slow 指向 2fast 变成 nullfast 为 null不补位反转 slow 开始的后半段就是反转节点 2 本身prev 指向 2比较left 为 1right 为 2值不相等返回 False。正确。再比如1 - 1比较时值相等left 和 right 都变成 null循环结束返回 True也正确。还有一个我在实际提交中遇到过的情况节点值可能是负数。比如[-129, -129]回文判断只比较 val 是否相等不涉及大小比较所以负数一样能跑。你只要别看到负数就觉得是无效输入就行。4.2 面试时需要留意的点面试的时候不要上来就写代码最好先按这个顺序跟面试官对齐先问清楚“可不可以修改输入的链表”。绝大多数情况下 LeetCode 允许但面试场景里有的面试官会故意设限。如果不能修改链表结构那 O(1) 空间的思路就失效了你需要用递归或者显式栈来从后往前访问链表空间复杂度升到 O(n)到时候要主动说明权衡。讲思路时一定要提奇数长度处理。我自己面试时说的原话是“快慢指针停在中间如果 fast 不为空说明是奇数长度中间节点不用比我让 slow 挪到右半段起点。”这句话基本是整道题的高光点多说一句面试官就知道你是真懂而不是背题。代码别写得过于花哨。有的同学喜欢把链表反转写成内部函数再调用个人不太推荐在紧张状态下引入过多函数栈。直接在 isPalindrome 里按顺序写完反而更清晰。如果面试官要求模块化再现场拆成辅助函数也不迟。5. 实战复盘从暴力解到 O(1) 空间的演进5.1 为什么转数组不是最优转数组方案代码确实简洁但它有三个隐藏问题一是额外空间 O(n)对大链表不友好二是它没有锻炼到链表操作能力换个变种题就抓瞎三是如果面试官接着问“如果链表很长放不进数组怎么办”你没法答。我之前还真在面试里被追问过这个。当时我先说了转数组解法面试官点头然后问我能不能优化空间。如果我只会背答案肯定接不住。所以后来我刷这道题时会刻意要求自己第一遍先用最直觉的方法写出来第二遍再强迫自己用 O(1) 空间重写两版代码放一起对比。这个方法对准备面试非常有效。需要说明的是转数组和快慢指针加反转都是正确的没有绝对好坏只有“在某个约束条件下更合适”。如果题目明确只求快速通过或者面试官说不管空间那转数组反而更省事。但作为经典题理解最优解仍然是必须的。5.2 递归方案的价值与局限链表回文还有一种递归做法维护一个外部指针 p递归访问到链表尾部然后在回溯过程中不断把 p 往右移和当前递归访问到的节点值比较核心逻辑大概是def check(head): nonlocal p if not head: return True if not check(head.next): return False if p.val ! head.val: return False p p.next return True这个方案思路很优雅天然实现了“一个指针从头往尾走一个指针从尾往头走”的效果。但它有两个明显局限第一递归深度等于链表长度链表长度到 10 万级别时Python 默认递归深度会报错C 和 Java 也存在栈溢出风险第二严格来说它借助了调用栈空间复杂度是 O(n)并不满足最优解要求。所以我觉得递归更适合作为理解链表回溯的思维实验不适合作为这道题的最终提交方案。面试时如果提到递归你可以这样收尾“递归思路能帮助理解但实际工程里我更倾向迭代避免栈溢出。”这句话显得你既有理论能力又有工程判断力。5.3 这道题在热门 100 题里的定位回文链表被收录在 LeetCode 热门 100 题Hot 100和经典题单里并不是偶然。它不像难题那样考高深算法而是把“找中点”“反转链表”“双指针比较”三个高频操作一次性串起来。这三板斧在链表题里几乎无处不在找中点是876. 链表的中间结点反转链表是206. 反转链表而回文链表就是它们的合体版。周赛里也经常能看到它的变体。可能不是直接叫“回文链表”而是换一个壳子比如“判断链表是否对称”“删除链表中最短回文子串”“在链表上做回文扩展”等等。热词里提到的周赛 430 虽然和这道题没有直接关系但你在周赛复盘时会发现很多链表题只要提取出“中点”和“反转”两个动作思路就会清晰很多。所以我的建议是这道题刷完之后不要四处找偏题怪题先把它的两个组件题各刷两遍再用回文链表做组合练习。这个组合套路一旦形成肌肉记忆你在后续刷其他链表题时会明显感觉顺畅很多。6. 常见问题与排查技巧实录6.1 本地测试通过但提交超时的原因超时多半不是因为算法复杂度而是因为代码里有死循环。回文链表这道题里最常见的死循环是反转链表时没有正确维护 nxt 指针。比如有的人会写成while cur: cur.next prev prev cur cur cur.next看起来没问题但仔细看第三步你在第二步已经改了 cur.next此时cur cur.next取的其实是更新后的 next也就是 prev于是 cur 又指回已经处理过的节点链表形成环循环永远出不去。调试时很容易发现程序卡住但新手经常盯着 while 条件看半天没意识到是 cur 步进错了。正确的写法是先保存原 next再改指针最后用保存的 nxt 步进。也就是本文前面写的那个三行顺序。我记得自己刚学的时候几乎每隔一周就会写错一次这一步后来索性总结成一句话“先存后改”就再也没错过了。还有一个隐蔽的问题是快慢指针找中点时fast 的判空顺序。如果你写成while fast.next and fast:当 fast 是 null 时会先访问fast.next直接抛空指针异常而不是返回正常结果。所以判空一定要把fast写在前fast.next写在后。6.2 如何用最小测试集自查我刷题的习惯是提交之前先在脑袋里或者本地跑几个最小用例不用多5 个就够覆盖主要分支[]空链表预期 true。[1]单节点预期 true。[1, 2]两个不同值预期 false。[1, 2, 2, 1]偶数长度回文预期 true。[1, 2, 3, 2, 1]奇数长度回文预期 true。再加一个特殊的[1, 2, 3, 1]这种不是回文的奇数长度预期 false。这 6 个用例跑完基本能把空指针、奇偶判断、比较退出条件全部覆盖到。如果本地跑某个用例失败先定位在哪一步。我建议在找完中点后打印 slow.val在反转完成后打印 prev 的链表这样能快速知道是中点找错还是反转写错。不要一上来就怀疑某个很远的环节链表题 90% 的问题都出在那几根指针的赋值顺序上。6.3 一点个人心得这道题我在一年多里反复写过不下十次每次写都有新的体会。最早是背答案后来是理解“奇数长度要跳过中间节点”再后来才意识到while right这个终止条件背后还藏着“后半段更短”这一层。最近一次写的时候我又问自己“如果不修改链表结构用读写不破坏原链表的方式能不能也做到 O(1)”答案是不行因为从本质上讲单链表要反向访问只能借助额外存储。能把这道题从“会写”讲到“为什么”就是我眼中真正刷透的状态。所以最后想分享的小技巧是如果面试时间充裕你可以在代码末尾主动提出“要不要我恢复链表结构”这通常是加分项。因为面试官看到的不只是你会解这道题还能看到你考虑副作用、具备基本工程素养。这篇复盘就是我目前对回文链表最完整的一份记录希望对你也有参考价值。
