如果你刷过力扣 Hot100大概率会在链表模块里碰到这道题回文链表。我第一次做的时候心想“判断回文谁不会”结果真上手才发现链表这玩意儿没法从尾部往前遍历别说写代码了光是想清楚怎么两头比对就够我喝一壶的。后来把这道题彻底吃透回头再看它反而觉得它是 Hot100 里链表题的一块“试金石”——知识点不深却把遍历、找中点、反转链表、边界判断全揉在了一起。这篇文章把我从暴力解法到标准解法的完整过程、踩过的坑、被面试官追问过的点一次性整理出来。不管你是刚刷到这道题还是在为面试突击链表题照着下面的思路走一遍应该能少走不少弯路。1. 题目拆解回文链表到底在考什么基本功1.1 一眼看上去简单动手却容易卡住先明确一下题目本身给一个单链表的头节点 head判断这个链表是不是回文链表是就返回 true不是就返回 false。回文的定义不用多说正着读和反着读一样比如1 - 2 - 3 - 2 - 1是回文1 - 2 - 3 - 1不是。数组里判回文两根指针一头一尾往中间走就行因为数组支持随机访问。但单链表只有 next 指针你拿着头节点能一路往后走却永远没法直接跳到最后一个节点再往回退。这就导致“两边往中间比较”的常规思路在链表上直接失效。很多人卡住不是因为不会判回文而是因为不熟悉链表的这个特性习惯性地拿数组思维去套结果发现无从下手。这道题适合谁刷我觉得是两类人一类是刷 Hot100 刷到链表板块想系统过一遍链表基本功的人另一类是面试前需要快速掌握链表高频考点的同学。它的难度在 LeetCode 上不算高但考察的东西非常集中属于那种“做会一道带动一片”的题目。1.2 核心考点链表遍历、快慢指针、原地反转拆开来看回文链表其实在考三个基础动作的组合。第一个是链表遍历这是底线中的底线。你得能在各种条件下安全地走完链表不会因为不小心访问了空节点的 next 而报 NullPointerException。第二个是快慢指针。要判断回文一个自然的想法是先找到链表的中点从中点把链表劈成两半然后拿前半段和后半段做对称比较。找中点这件事最优雅的方式就是快慢指针快指针一次走两步慢指针一次走一步快指针到尾部时慢指针刚好落在中间位置。这个技巧在 Hot100 里的出现频率极高环形链表、链表中点、链表重排全都能用上。第三个是反转链表。找到中点之后想要“从后往前”比较单链表本身做不到那就把后半段原地反转过来。反转之后就得到了一个可以从尾部方向遍历的“假想逆向链表”再跟前半段从头开始逐一比对。反转链表本身也是 Hot100 的常客两道题叠加在一起正好是一次综合练习。1.3 解法的整体取舍时间和空间的权衡力扣这道题的进阶要求是时间复杂度 O(n)、空间复杂度 O(1)。很多第一次刷的人看到这个要求会愣一下判断回文难道不是必须把链表存下来吗其实不用靠快慢指针加原地反转确实可以做到常数级额外空间。有意思的是单纯满足“能判断回文”其实有非常多办法比如转成数组、用递归、甚至用栈。这些办法写起来可能更直观但要么空间复杂度超标要么实现起来华而不实。面试和刷题场景下我们需要的不只是“能跑通”而是“在约束下跑得漂亮”。所以这篇文章后面会用一整章来对比不同解法的取舍带你看清楚为什么最终标准答案长那样。我个人的建议是先掌握最简单的数组法用来保底再把快慢指针反转的方案练成“肌肉记忆”。这两种方案在手这道题基本就稳了。2. 三种解法实测对比数组、递归、快慢指针反转2.1 数组法最直观的入门解空间不够看数组法的思路简单到不能再简单遍历一遍链表把所有节点的值按顺序存进数组然后用两根指针从数组两端向中间移动逐一比较。def isPalindrome(head): 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)。它的优点非常明显好想、好写、不容易出错特别适合第一次见到这道题时用来确认题意、打底。但缺点同样明显节点数量一旦上到十万级就需要额外开一个等长的数组在内存敏感的环境里不合适更不符合题目进阶要求的 O(1) 空间。不过别小看这个“笨办法”。实际面试里如果你先快速给出数组法再主动说“但这样空间是 O(n)我可以用快慢指针反转优化到 O(1)”面试官会觉得你思路清晰、知道权衡。直接甩出最优解当然也行但很多人其实是背下来的被追问两句就露馅。数组法作为铺垫反而能展示你的思考过程。2.2 递归法逻辑对称但栈深度是硬伤递归法的思路也很有意思。它利用递归调用栈天然具有“先入后出”的特性让函数一路递归到链表尾部然后在回溯的过程中和链表头部方向的一个“左侧指针”逐一比较。核心想法是每层递归拿到的是“右侧节点”同时用一个外部变量维护“左侧节点”。左侧指针初始指向头节点每次比较完就往右挪一格。这样递归一层层往回走左侧指针一步步往右走两边就实现了“对称相遇”。def isPalindrome(head): front head def check(cur): nonlocal front if cur is None: return True if not check(cur.next): return False if front.val ! cur.val: return False front front.next return True return check(head)这个解法逻辑上很优美代码也短但它有两个致命问题第一递归深度等于链表长度链表一长调用栈直接溢出第二从复杂度角度讲它的额外空间依然是 O(n)因为每层递归都要占用栈帧。所以它更适合用来“理解递归的回溯过程”而不是当作实战首选。面试的时候如果你提递归可以强调“我能讲清楚原理但不会用在大数据量场景”。2.3 快慢指针反转面试标准答案真正符合 O(n) 时间和 O(1) 空间的方案核心就三步先用快慢指针找到中点然后反转后半段链表最后把前半段和反转后的后半段逐节点比较。这个方案为什么是标准答案因为它把链表题里最高频的两个技巧组合在了一起既展示你对链表指针的掌控力又展示你对空间复杂度的敏感度。而且它还有一个隐藏加分项比较完之后可以再把后半段反转回来恢复链表原有结构。这样函数执行前后链表完全不变在很多“不允许破坏输入数据”的场景里很重要。三种方案的对比我整理成了一张表方便你一眼看清差异解法时间复杂度空间复杂度是否改变原链表适合场景数组 双指针O(n)O(n)否新手入门、快速保底递归对称比较O(n)O(n) 调用栈否理解递归回溯不推荐实战快慢指针 反转O(n)O(1)是可恢复面试标准答案、满足进阶要求个人体验是数组法帮我建立了题目的基本认知递归法帮我理解了什么叫“用调用栈模拟逆序”而真正让我在面试里不畏追问的还是快慢指针反转这个方案。接下来我就把这一套方案的每一行代码掰开揉碎讲给你听。3. 完整实操用快慢指针原地反转一步步实现3.1 第一步快慢指针找中点为什么偏偏是它快慢指针找中点的原理可以想象成两个人在跑道上跑步一个人速度是另一个人的两倍同时出发等快的人跑到终点时慢的人正好在跑道中间。映射到链表里就是fast一次跳过两个节点slow一次走一个节点。不过在写代码之前要先想清楚一个问题中点到底停在哪里链表长度可能是奇数也可能是偶数。奇数长度比如1 - 2 - 3 - 2 - 1中点就是正中间那个3。偶数长度比如1 - 2 - 2 - 1没有正中间节点我们一般说“中点”是在两个中间的节点之间此时把链表分成前后两段更合适。为了后续处理方便我推荐一个固定写法让slow停在前半段的最后一个节点上后半段的起点用slow.next表示。实现起来也不难slow, fast head, head while fast.next and fast.next.next: slow slow.next fast fast.next.next可以自己手动模拟一下1 - 2 - 3 - 2 - 1循环结束后 slow 停在节点3后半段是2 - 1正好把中间节点留在前半段。1 - 2 - 2 - 1循环结束后 slow 停在第一个2后半段是第二个2 - 1两半长度相等。这个定位方式的好处是它天然把中间节点归给前半段后半段永远是从一个对称的、长度不会超过前半段的节点开始的后面比较时会更安心。如果你让 slow 停在偏右的位置也不是不行但比较循环的条件就要额外小心这一点我放到第 4 章再展开。3.2 第二步原地反转后半段三指针到底怎么挪反转单链表是每个写链表题的人必须闭着眼睛都能写出来的基本功。这里用最经典的迭代三指针法prev指向已经反转好的链表的头cur指向当前要处理的节点nxt用来保存cur原本的下一个节点防止指针被改写后找不回来后半段。prev None cur slow.next while cur: nxt cur.next # 先保住还没处理的下一个节点 cur.next prev # 把当前节点指向前一个节点实现“掉头” prev cur # prev 前移成为新的已反转链表头 cur nxt # cur 继续处理下一个原始节点很多人第一次写反转链表时都会犯同一个错直接把cur.next prev写了却没有先保存cur.next的值。一旦执行完这一步后半段剩下的节点就全部丢了链表断成两截。打个比方就像搬家时你没在旧地址留钥匙人一搬走就再也进不去了。反转完成后prev指向的就是原链表后半段的“头”也是反转后后半段的头。命名上我喜欢叫它right_head因为接下来比较阶段它就是右侧遍历的起点。这里要注意slow.next现在已经被改变了它指向的是反转后的后半段头也就是原链表的最后一个节点。3.3 第三步两侧逐一比较循环条件千万别写错比较阶段就清爽了。左侧从头节点head开始右侧从right_head开始两个指针同步往后移动只要发现值不相等直接返回 false如果右侧链表走完了还没发现不等就说明是回文。left head right right_head result True while right: if left.val ! right.val: result False break left left.next right right.next这里的循环条件我推荐用while right而不是while left。原因在于right_head指向的后半段长度一定不会超过前半段。用right做条件可以保证比较一定在合理范围内结束不会出现 left 已经走出头但 right 还有节点没比完的情况。整个比较过程天然兼容奇数长度的链表中间那个多余的节点直接被忽略掉了因为右侧链表里本来就没有它。这个细节看着不起眼但面试时很多人就是在这里翻车的。循环条件写错要么越界要么漏比较最后一个节点属于那种“代码跑一遍没问题换个例子就炸”的典型隐患。3.4 第四步还原链表结构面试追问的加分项比较完之后链表其实是“变形”状态后半段是反的。如果函数执行完调用方还想继续使用这个链表就会拿到一个结构被破坏的数据。力扣判题系统通常不会检查这一点但面试官经常会追问“这个解法修改了原链表如果不允许修改呢”这时候如果你能主动说出“我可以把反转的后半段再反转回来恢复原链表结构”印象分会明显不一样。恢复的操作本质上就是再反转一次把right_head这段链表重新反转让它回到原来的顺序然后把它重新接回slow.next。prev None cur right_head while cur: nxt cur.next cur.next prev prev cur cur nxt slow.next prev执行完之后原链表就完整回复原样了。这里有一个很关键的操作细节在比较阶段你不能把right_head弄丢。比较时right指针会一路往后移动最后指向 nil所以要在反转后半段之后、开始比较之前把right_head单独存好。否则比较完想恢复的时候你根本不知道要从哪里开始恢复。这个坑我在模拟面试里踩过一次当时花了半分钟才反应过来。3.5 完整代码与复杂度分析把上面四步串起来完整代码长这样class Solution: def isPalindrome(self, head: Optional[ListNode]) - bool: if not head or not head.next: return True # 1. 快慢指针找中点slow 最终停在前半段的最后一个节点 slow, fast head, head while fast.next and fast.next.next: slow slow.next fast fast.next.next # 2. 反转后半段right_head 是反转后的后半段头 prev None cur slow.next while cur: nxt cur.next cur.next prev prev cur cur nxt right_head prev # 3. 前半段和反转后的后半段逐一比较 left head right right_head result True while right: if left.val ! right.val: result False break left left.next right right.next # 4. 恢复原链表把后半段再反转回去重新接上 prev None cur right_head while cur: nxt cur.next cur.next prev prev cur cur nxt slow.next prev return result复杂度这块很干净找中点遍历大概 n/2 个节点反转后半段遍历 n/2 个节点比较遍历 n/2 个节点恢复再遍历 n/2 个节点。整体时间复杂度是 O(n)额外空间只用了几个指针变量O(1)。无论链表多长这个解法都不会额外申请和链表长度相关的内存空间。如果你用的是 C 或者 Java逻辑完全一样只是指针操作显得更“硬”一点。Java 里注意ListNode引用别弄丢C 则要留意手动管理别把节点给 delete 了不然恢复链表时直接炸。4. 手写过程中高频踩坑问题与排查实录4.1 快慢指针到底用哪个 while 条件这是这道题问得最多的问题为什么用的是while fast.next and fast.next.next而我经常看到别人写while fast and fast.next两种写法都能用关键区别在于slow最终停在的位置不同while fast and fast.next循环结束后slow停在偏右的位置也就是后半段的起点奇数长度时它指向中间节点。此时反转要从slow开始比较时左右长度可能右边更长一丢丢循环条件要小心。while fast.next and fast.next.next循环结束后slow停在前半段的最后一个节点后半段从slow.next开始。奇数长度时中间节点归前半段后半段长度绝不会超过前半段。我推荐第二种因为它让后续的反转和比较都更省心。但如果你习惯第一种也不是不行只不过写的时候要多想一层。面试时关键在于你能说清楚自己的写法对应的是哪种中点定义能自圆其说即可。4.2 反转链表时指针丢失反转链表的“夺命三指针”最常见的错误就是没保存nxt就直接改cur.next。一旦执行cur.next prev原链表的后半段就再也访问不到了代码表现上通常是程序没报错但比较的结果莫名其妙不对或者链表看起来“只剩一节”。排查这种问题有个笨但有效的方法反转前后各打印一遍整条链表亲眼看看哪一步开始断裂。写成代码大约是def print_list(node): while node: print(node.val, end - ) node node.next print(None)反转前打印一次反转后打印一次马上就能看出来指针有没有丢。真机debug的时候这种可视化手段比直接盯着代码猜快得多。4.3 比较时循环条件用错导致越界或漏比我见过有人写while left或者while left.next这两种都有隐患。用while left时左边的链表可能比右边长奇数中间节点归前半段的情况即使全部节点都相等也会在 right 已经走到头之后继续访问 left 那边的多余节点此时如果用到了right.val就会出错只比较left不检查right又可能出现左右错位。最稳的判断就是while right因为右侧永远是较短的那一段。右侧走完说明该比较的对称位置全都比过了直接返回 true 即可。你也可以顺手加一个防御性判断如果left走到头但right还有节点说明两半不对称直接 false。不过按照我们前面的中点定位方法这种情况理论上不会出现。4.4 忘了还原链表被面试官追问如果你在面试中写的是修改链表的解法面试官几乎一定会追问原链表被你改掉了怎么办通常的追问思路是先问“你意识到你的解法改变了输入吗”再问“能不能不改变链表结构”。应对思路有两个方向明确说明这道题可以接受修改链表因为题目没有说不能改但如果后续还需要使用这个链表我就需要恢复。直接展示恢复逻辑把反转后的后半段再反转回来接回slow.next。这也是我在 3.4 节里展示的做法。不要一上来就说“不需要恢复”那样会显得你对函数副作用不敏感。能主动恢复是体现工程素养的加分细节。4.5 空链表和单节点边界虽然力扣上这道题的约束通常是链表至少有一个节点但写代码时养成防御性检查的习惯没有坏处。开头加上if not head or not head.next: return Truehead为空空链表算回文只有一个节点也算回文同时也能避免后面访问head.next时报空指针。这个判断看起来多余但在面试里你如果能主动说出来会显得你考虑边界条件很周全。相比之下很多人在这个位置栽过跟头——主流程写得飞起结果一跑空链表直接 crash。把上面这些坑汇总成一张速查表平时复习时扫一眼就够了常见错误出错原因正确做法快指针无限循环while 条件写成了while fast用while fast.next and fast.next.next保证 fast 能正常推进反转后半段丢节点没保存cur.next就改写指针用nxt cur.next先备份再反转比较结果不稳定循环条件用while left改用while right右侧更短更安全链表结构被破坏忘了恢复反转两次比较前反转后半段比较后再反转一次空节点访问没判断输入为空/单节点函数开头防御性检查5. 这道题放在 Hot100 里该怎么刷才值5.1 Hot100 里链表题的共同内核力扣 Hot100 作为最经典的高频题单里面的链表题其实有一个共同的内核指针操作。反转链表练的是指针改向环形链表练的是快慢指针的运用删除倒数第 N 个节点练的是间隔指针两数相加练的是指针遍历和进位维护。回文链表几乎是唯一一道把所有基础动作一次性串起来的题。刷的时候我建议你别只满足于“AC 了就行”。如果你能把这道题的四个步骤拆开每一步都问自己“为什么这一步要这样做”“有没有替代方案”那这一题刷完的收益可能抵得上盲目刷十道题。还有一个很现实的角度Hot100 是面试高频题的集合回文链表在这张表里是链表模块的常驻题目。面试里碰到原题改编的概率不低比如改成“判断回文串但是链表存储”“找到链表的中点”“反转链表的前半段”等等。底层能力打通了变形题就只是换层皮。5.2 一道回文链表带动一整套链表基本功如果你是自己刷题我建议按这个顺序来做一次“组合训练”先去把“反转链表”单独练熟。反转是整个链表系列的地基回文链表、重排链表、K 个一组翻转链表全都要用到它。可以找一道纯反转链表的题把迭代三指针法和递归法都写一遍直到闭着眼能写出来。再去练“环形链表”或者“找链表中点”把快慢指针的语义彻底搞清楚。理解快指针走两步、慢指针走一步到底会发生什么为什么能相遇为什么能定位中点。最后回过头来做回文链表。这时候你会发现前面练的两种能力自然衔接整个过程非常顺畅。这种方法比直接死磕回文链表要高效因为你在分别建立局部肌肉记忆再组合成整体方案而不是试图一口气记住一堆指针操作。5.3 我的个人刷题心得说实话我在这个平台上刷题这么久回文链表是我印象很深的一道题。第一次做的时候我用的就是数组法当时觉得这题简单几分钟写完就过了。后来在模拟面试里被面试官追问“能不能 O(1) 空间”我当场卡壳回去才老老实实把快慢指针反转的思路推演了一遍。也正是那一次之后我开始养成了一个习惯链表题先画图再写代码。找中点画一遍反转变换画一遍比较过程再画一遍。画图看起来慢实际上是在帮你把指针之间的指向关系在脑子里建模。等你把这类题的“手感”养出来再写反转、再写快慢指针基本就是条件反射了。如果你现在正卡在这一题别急着背代码拿起纸笔画一条1 - 2 - 3 - 2 - 1跟着快慢指针一步步走再把后半段反转、比较、恢复的每一步都标出来。画懂了代码自然就写得出来。链表题拼的从来不是智商而是手感和对指针更新的肌肉记忆而回文链表就是帮你把这种肌肉记忆打下基础的那道题。