回文链表O(1)空间解法：快慢指针与反转链表实战

先说实话LeetCode Hot100 做到第 21 题迎面撞上 234. 回文链表是很多人的“分水岭”。这题我在准备面试时被问过两次一次是电话面一次是现场手撕也看过太多同学习惯性先转数组、然后被面试官一句“能不能 O(1) 空间”问到卡壳。今天这篇不打算只给一个能过的答案而是把这道题背后的判断逻辑、四种解法的取舍、以及实操中那些肉眼看不见的坑一次说透。先说清楚题目本身给定一个单链表的头节点 head判断这个链表从头到尾读、从尾到头读是否完全一致。比如1 - 2 - 2 - 1是回文1 - 2 - 3不是。单链表的特性是只能从 head 一步步往前访问不能回头也不能随机访问所以“回文”这个看似简单的对称判断放到链表上就变难了。这道题适合正在刷题找工作的人、准备面试但链表基础不牢的人以及想搞懂快慢指针和链表反转真正原理的人。全文我会按“思路演进 - 最优解原理 - 代码细节 - 错误实录 - 套路总结”的顺序展开尽量让你不只是背会而是真的会。1. 一道链表题为什么能常驻 Hot1001.1 题目到底在考什么回文判断本身不难数组版本三分钟就能写出来两个指针一左一右往中间走比到不相等就返回 false。但链表把这个“不难”变得“不简单”因为它恰好踩中了链表的三个核心痛点单向链表只能从 head 往下走想要“从尾到头”天然缺一条反向通路想比较对称位置需要同时知道两端节点但链表没有随机访问能力如果要求空间复杂度 O(1)就不能用数组、栈这类辅助结构必须靠改变指针方向来创造“反向遍历”的条件。所以 Hot100 选它不只是因为它考了“是否会反转链表”更重要的是它考你有没有一种能力遇到“需要从两个方向同时遍历”的问题时能不能想到“把其中一段反转用空间换不了就用手艺换”。这道题的价值在于它是很多链表高级操作的集合题——快慢指针、链表反转、边界处理全在一道题里扎堆出现。1.2 三种主流解法的思维链路我刷这题时脑海里过过三条路每一条都有它存在的道理面试时也可以按这个顺序说给面试官听正好展示你的思考递进。第一条路是“数组翻译法”。遍历链表把每个节点的 val 存进 vector然后用数组双指针判断。这是最直观的做法复杂度是 O(n) 时间、O(n) 空间。优点是绝对不可能出错代码五分钟写完调试也容易缺点是空间占用大一旦面试官限制 O(1) 空间这条路直接封死。第二条路是“递归反向法”。利用递归函数一层层压栈在真正比较时从最后一个节点开始往前返回配合一个从头往后走的前向指针。代码可以写得很短但本质上是用了系统调用栈作为额外空间仍然逃不掉 O(n) 的空间复杂度。而且链表很长时递归深度过大会有爆栈风险所以实战里我一般只在“说出思路但不用它实现”的场景提起。第三条路就是最优解快慢指针定位中点把后半段链表原地反转然后两个半段从头开始逐一比对。这个方案把空间复杂度压到 O(1)时间仍然是 O(n)。后面我讲的每一个细节都围绕这条路展开。2. 手撕最优解快慢指针 反转后半段2.1 核心代码C先直接给完整的可运行实现我在 LeetCode 默认的链表结构下把代码整理成下面这样/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ ListNode* reverseList(ListNode* head) { ListNode* pre nullptr; ListNode* cur head; while (cur) { ListNode* next cur-next; // 先存下原来的下一个节点 cur-next pre; // 把当前节点的指针指向前一个 pre cur; // pre 向前移动 cur next; // cur 继续沿原链走 } return pre; // 反转后 pre 就是新链表的头 } bool isPalindrome(ListNode* head) { if (head nullptr || head-next nullptr) { return true; } // 第一步快慢指针找中点 ListNode* slow head; ListNode* fast head; while (fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; } // 第二步反转后半段包括 slow 开始的全部节点 ListNode* second reverseList(slow); // 第三步前半段和后半段逐个比较 ListNode* first head; ListNode* secondCopy second; // 留一份用于最后还原链表 bool result true; while (second ! nullptr) { if (first-val ! second-val) { result false; break; } first first-next; second second-next; } // 第四步把后半段再反转一次恢复原链表 reverseList(secondCopy); return result; }这段代码里我特意加了一个很多人会忽略的步骤最后把链表还原。LeetCode 的判题大概率不会因为你改了原链表就报错但真实面试里面试官通常会在你写完以后追问一句“你这个函数会把输入链表改掉如果有别的线程正在读这个链表怎么办”所以养成“用完恢复原状”的习惯不只是风格问题更是安全意识的问题。2.2 为什么快慢指针能找到中点快慢指针的原理其实是个“速度差”的问题slow 每次走一步fast 每次走两步。当 fast 走到链表末尾时slow 恰好走了 fast 一半的路程自然就落在整个链表的中间。举个例子链表长度是 6。fast 每次跳两步它会依次经过节点 1、3、5然后到达 nullptr 停下。此时 slow 依次经过 0、1、2最后停在节点 2下标从 0 开始数。你会发现对于偶数长度slow 正好落在右半段的第一个节点上也就是反转的起点。链表长度是 5 时fast 依次走 1、3、5最后停在最后一个节点slow 依次走 0、1、2停在正中间那个节点。所以无论奇偶这个算法都能用一个循环搞定定位不需要额外判断链表总长度这就是它优雅的地方。我在代码里写的循环条件是while (fast ! nullptr fast-next ! nullptr)。这两个条件缺一不可fast ! nullptr保证访问 fast 本身合法fast-next ! nullptr保证下一步 fast-next-next 不会越界。奇数长度的链最后一次循环结束后 fast 停在尾节点fast-next 是 nullptr循环退出偶数长度的链fast 最终走到 nullptr 本身循环退出。你要是不写 fast 的非空判断偶数长度下第一次进循环就可能踩段错误。2.3 反转链表为什么必须用“三指针”反转是这道题里最容易写乱的部分。新手常见的错误是把 cur-next 改成 pre 以后发现找不到原来的下一个节点了——因为原链已经被你切断。所以标准的迭代反转必须用三个指针pre、cur、next。每次先把 cur 的下一个节点用 next 存起来再放心大胆地把 cur-next 指向 pre然后三兄弟整体右移。这里有个我自己的理解方式把前两步“存 next”和“改指向”看成一个不可拆分的先备份、再破坏的过程。你只有先记住下一站在哪才敢把当前的指针掰向反方向。这一招熟练之后不只这题能用反转部分链表、K 个一组反转链表全部通用。反转完成后返回的 pre 就是反转后新链表的头。举例来说原链表是1 - 2 - 2 - 1快慢指针停在第二个 2 上0 下标是 1下标 1 是 2下标 2 是另一个 2反转从这个节点开始得到一条新的子链1 - 2方向和原来相反。此时把它和前半段1 - 2逐个比正好一一对上。2.4 复杂度分析为什么它是 O(1) 空间时间上快慢指针扫了半个链反转半个链再比较半个链每一步都是 O(n) 量级的常数倍合起来仍然是 O(n)。空间上从头到尾只用到了 pre、cur、next、slow、fast 这几个固定指针没有任何随输入规模增长的存储结构因此是严格的 O(1) 空间。这也是这道题作为“最优解”与“数组解”最本质的区别数组解的空间是 O(n)数据量一大会明显吃内存指针方案不管链表多长内存占用始终是几个变量。3. 边界条件与高频错误实录3.1 空链表与单节点代码开头有一行if (head nullptr || head-next nullptr) return true;这行我在刷题时曾经觉得多余直到某一次删掉它之后在空链表上直接段错误才意识到边界条件的意义。空链表没有对称性可言但题目语境下空链表也就是只包含零个元素的序列它天然是回文单节点链表的头尾就是同一个节点必然与自己相等所以也直接判 true。这行处理不只在本题有用很多链表题都有类似的先头判断建议当作肌肉记忆写进去。3.2 奇偶长度的差异化表现我用一个表格把奇偶情况讲清楚因为这是最容易困惑的地方链表长度快慢指针结束时 slow 的位置反转后的后半段长度比较次数2偶数第二个节点113奇数中间节点224偶数第三个节点225奇数第三个节点中间33奇数长度时 slow 落在正中间这个中间节点会被反转进后半段而且比较时会出现一次“自己和自己比”的情况比如长度 5第一次比较是头部节点和尾部节点第二次是第二个节点和倒数第二个节点第三次就是中间节点和自己。这不会影响最终结果因为 a 和 a 必然相等。奇数长度的正确性在于中间节点自己等于自己多比一次也无所谓。偶数长度时slow 恰好在右半段开头不存在中间节点两半段长度完全相等。理解了这个差异你再看不同的题解代码里有没有额外一行“奇数时 slow 要多走一步”就明白为什么有人写、有人不写。我的代码选择不额外处理逻辑更统一也好解释。3.3 让人血压升高的四个典型 Bug这题我见过太多人踩雷包括我自己第一次写的时候也踩过。我把它们一条条列出来你踩过了就能绕开。第一个 Bug快慢指针循环条件写错。写成while (fast-next ! nullptr)看着没什么问题但偶数长度的链会让 fast 走到 nullptr下一次循环访问 fast-next 的时候直接段错误。正确写法必须是while (fast ! nullptr fast-next ! nullptr)两个条件一个都不能省。第二个 Bug反转链表时弄丢下一个节点。有人写cur-next pre;之后才去找 next结果链已经断了后面全是野指针。这个问题其实很好规避就是严格执行“先存 next、再改指向”的顺序这和我前面讲的三指针逻辑是一致的。第三个 Bug比较循环的终止条件写错。有同学喜欢写while (first ! second)但两条子链长度可能不同尤其是我这种不额外移动 slow 的写法第一段会包含中间节点直接比较指针位置会提前退出或者死循环。最稳妥的终止条件是while (second ! nullptr)因为比较链路中 second 是反转后的后半段它先走到 nullptr 的时候前半段即使多出一个中间节点也无所谓。第四个 Bug反转后忘记还原。不还原时 LeetCode 能过但面试里一旦被追问“你改了输入数据如果被其他地方复用怎么办”就非常被动。解决办法是在反转前把反转后的子链头保存下来代码里的 secondCopy比较结束后再对其实行一次完整的 reverseList链表就恢复原状了。这一步时间开销同样是 O(n)/2复杂度没有变化但安全性高很多。4. 从回文链表看链表题的通用法则4.1 链表三板斧刷完这题你会发现大部分主流链表题都逃不开三个核心操作快慢指针、链表反转、哑节点。回文链表用了前两个重排链表和环形链表检测也用了快慢指针反转链表系列则是把第二个用到极致。这里特别想强调这三板斧不是独立的技巧而是会在同一道题里组合出现的积木。比如 143. 重排链表就是“找中点 反转后半段 交替拼接”三步走和回文链表的前半部分几乎一模一样。如果你今天能把回文链表写到顺手重排链表对你来说大概只需要额外十分钟。哑节点这题没直接用到但它也是链表题里一个极好的习惯。凡是头节点可能被删除、插入、变更的题都可以在 head 前面加一个 dummy 空节点让头节点退化成普通节点这样就不用单独处理“头节点变了”的特例。回文链表虽然没有改头节点但你还原链表时保不齐会有断链的瞬间多一层 dummy 往往能让你的代码更稳健。我的建议是这三样技术混着练每道链表题做完以后都想想“这里面有没有三板斧的影子”比单纯刷数量有用的多。4.2 同类题目的思维迁移回文链表解决的核心矛盾是“单链表只能正向遍历”而它的解法把它拆成了两个子问题先拿到后半段的正确起点再让后半段可以反向遍历。前面一个子问题用快慢指针解决后面一个子问题用反转解决。这个“拆解矛盾”的思路本身可以直接迁移到几道其他高频题上反转链表只考反转本身是基本功链表的中间结点只考快慢指针找中点是这条思路的入口题环形链表快慢指针找相遇点核心还是速度差重排链表找中点 反转后半 拼接是回文链表的完整进阶版回文链表两个子问题的组合也是我们今天的主角。如果你把这几道题放在一个下午集中刷会明显感觉到“肌肉记忆”的形成。快慢指针的循环条件、反转的三个指针写多了以后就变成条件反射不用每次重新推导。4.3 面试现场怎么答这道题这道题出现在面试里的概率很高因为它区分度好。完整的回答策略我建议分三步走。第一步先给最朴素的方案。主动说“我可以用一个数组存所有节点值然后双指针判断”同时报出复杂度是时间 O(n)、空间 O(n)。这一步是给沟通留一个锚点也让面试官知道你会主动分析复杂度。第二步主动提出优化。在面试官追问之前自己说“但这题数据规模大的时候可以在 O(1) 空间内完成思路是先用快慢指针找到中间位置再把后半段反转后逐节点比较。”这里提前亮出优化点比被动等问题再回答要舒服得多。第三步手写代码时一边写一边把关键点的原因讲出来。比如循环条件为什么要检查 fast 和 fast-next、反转前为什么要存 next、比较后为什么要还原原链表。面试官最怕的不是写不出来的人而是写出来但说不清楚为什么的人。你边写边解释这几点往往比单纯“咔咔一顿输出”的分数更高。最后再分享一个我刷完这道题之后保留的习惯每次写完链表题我都会用四个必测用例检查一个函数——空链表、单节点、偶数长度回文、奇数长度回文。今天这个程序我也建议你亲自跑一遍这四种输入把奇偶情况的指针走向在纸上画清楚。这道题真正越过“背代码”门槛的标志是你闭上眼能说出“slow 停在哪儿、反转从哪儿开始、比较到什么时候停”——能做到这一步LeetCode Hot100 的第 21 格就算真正踩实了。