空间解法)
链表回文这种题说实话算是链表操作里的“分水岭”。OR36这道题刷题平台上的题号记不太清但内容我闭着眼都能画出来给一条单链表判断它是不是回文结构就是说链表的节点值序列从左往右读和从右往左读是否完全一致。比如 1-2-3-2-1 就是回文1-2-2-1 也是回文而 1-2-3-1 就不是。很多新手第一次看到这题第一反应就是“这不简单嘛转成数组再用双指针从两头往中间比”。能这么做但面试官大概率会追问一句“能不能优化到 O(1) 的空间复杂度”这个时候如果你只会数组法基本就卡住了。这篇文章不打算给你灌鸡汤就老老实实把这道题从暴力到最优全部拆开数组法、递归法、快慢指针 反转后半段的最优解每一段代码都给你每一步为什么这么写、坑在哪儿也都讲明白。不管你是刚开始刷链表题的小白还是准备面试想把手撕算法练熟的选手这篇都值得看完。尤其是那些“看似对了、一跑就崩”的边界条件我会全部摊开来聊。1. 题解核心思路拆解1.1 回文链表到底在考什么回文Palindrome这个概念大家不陌生字符串、数组里判断回文非常简单左右两个指针往中间走逐个比较就行。但换到链表上问题就来了。单链表是单向的只能从头往后遍历你没办法像数组那样随机访问“倒数第几个节点”。所以这道题表面上问的是“是不是回文”实际上考的是三个链表的底层基本功怎么在单链表中找到中间节点怎么把一条链表原地反转怎么处理奇偶长度带来的边界值差异这三个点恰好覆盖了链表操作里最常见、最核心的技法。所以这道题才被很多面试官当成“试金石”题——代码量不大但考察点不少写得干净利落的人基本功基本不会差。1.2 从回文定义反推设计思路回文的本质是前半段与后半段“逆序后”相等。比如长度为 5 的链表 1-2-3-2-1前半段是 1、2后半段是 2、1把后半段反转后就是 1、2正好和前半段相等。中间那个 3 是“中心”不需要参与比较。想通这一点解决方案就呼之欲出先找到链表的中点把中点之后的节点整体反转用两个指针一个从正数第一个节点走一个从原链表尾节点反转后的新头走逐个比较如果比到最后都相等就是回文否则不是。这就是最优解的核心脉络。后面的所有代码都是围绕这条主线展开的。1.3 为什么首选快慢指针而不是先求链表长度有人可能会想既然要找中点我直接先遍历一遍求出链表长度 n然后走 n/2 步找到中点不就行了吗确实可以时间复杂度也是 O(n)代码写起来甚至更直观。但在链表题里快慢指针是更高频、更通用的技巧。它的优势在于只遍历一遍就能找到中点不需要额外维护“长度”这个变量处理环形链表、找倒数第 k 个节点等场景时同样适用。当然面试的时候如果你先讲求长度法再讲优化成快慢指针这个思路推进过程本身也是加分项。但最终给出的最优解一定是快慢指针。1.4 先想清楚空间复杂度的取舍这道题最容易被诟病的就是“用数组存值”。数组法的空间复杂度是 O(n)在数据量小的测试用例下看不出问题可一旦链表长度来到百万级额外分配一个百万长度的数组既不优雅也不靠谱。递归法虽然代码很漂亮但递归栈深度等链表长度依然是 O(n) 空间长链表还可能栈溢出。真正能达到 O(1) 空间的只有“反转后半段 双指针比较”这种做法。所以在正式讲代码前你要有一个意识解链表题和做业务需求一样先看限制条件最严的场景。如果题目没有明确说不能改链表结构那么反转后半段是性价比最高的选择。2. 从暴破到最优三种解法逐个拆解2.1 解法一复制到数组双指针往中间扫这个方法最直白。第一次遍历链表把所有节点的值按顺序塞进一个数组然后用数组双指针一头一尾往中间比较。核心代码大概是这样的以 C 为例bool isPalindromeByArray(ListNode* head) { vectorint vals; ListNode* p head; while (p ! nullptr) { vals.push_back(p-val); p p-next; } int left 0, right vals.size() - 1; while (left right) { if (vals[left] ! vals[right]) { return false; } left; --right; } return true; }这个解法的优势非常明显简单、不容易出错基本不需要考虑链表指针细节。缺点也很明显如果链表特别长数组会占用大量额外空间而且在某些面试场景下面试官会直接追加一句“不能用额外容器”那这个方法就彻底废了。需要强调的是这并不代表它“不好”。对于实际业务里那些长度可控、又不要求极低内存的场景数组解法足够可靠。刷题和面试你得学会在不同条件下切换思路。2.2 解法二递归后序遍历模拟双端比较递归解法的思路非常巧妙链表天然是线性的所以我可以先递归到最后一个节点然后在“回溯”的过程中让一个“外部指针”从头开始往前走这样一前一后就能进行比较。举个例子链表是 1-2-3-2-1递归函数一层层深入递归到节点 5值 1回溯到它时外部指针指向节点 1值 1比较相等外部指针后移继续回溯到节点 4值 2此时外部指针指向节点 2值 2比较相等继续回溯到节点 3值 3外部指针指向节点 3值 3相等之后所有回溯节点都比较完毕返回 true。C 代码一般写成这样class Solution { private: ListNode* front; public: bool check(ListNode* node) { if (node nullptr) { return true; } bool result check(node-next); // 后半部分比较已经失败的话直接短路 result result (front-val node-val); front front-next; return result; } bool isPalindromeByRecursion(ListNode* head) { front head; return check(head); } };这个解法的代码非常短但有两个致命短板递归深度等于链表长度空间复杂度是 O(n)当链表太长时递归栈会溢出程序直接崩掉。所以它更适合作为“思路展示”给面试官看不适合作为最终的线上答案。不过理解递归回溯的过程对理解树、图这类结构性数据的遍历也有帮助不妨练一练。2.3 解法三快慢指针找中点 反转后半链表现在来到正题。这个解法的精妙之处在于它把链表拆成了两半后半段原地反转然后和前半段逐个比较。整个过程只需要有限的几个指针变量空间复杂度 O(1)。先分四步走第一步处理特殊情况空链表和只有一个节点的链表天然就是回文直接返回 true。第二步用快慢指针找中点。慢指针每次走一步快指针每次走两步。当快指针到达链表尾部时慢指针正好停在中间偏右的位置上。这一步需要特别注意循环条件我在后面第 3.2 节里会专门展开。第三步从慢指针所在位置开始把后半段链表彻底反转。反转之后原本链表的尾部变成了“新后半段”的头节点。第四步用两个指针分别从原链表头和反转后的后半段头开始同步往后走逐一比较每个节点的值。只要有一对不同直接返回 false。如果后半段全部比完还没发现差异就说明是回文。这个思路不仅是这道题的答案也是很多链表题的通用套路找中点 反转 合并 / 比较。掌握它比单纯背会一道道题有用得多。2.4 三种方式对比一张表看清差距方案时间复杂度空间复杂度是否破坏原链表代码复杂度适用场景数组 双指针O(n)O(n)否极低链表较短、对空间没要求的场景递归后序比较O(n)O(n)否低思路展示、短链表快慢指针 反转后半O(n)O(1)是中面试标准答案、大型链表注意第三种方案会破坏原链表结构。后面我们来讨论这个点怎么应对。先记住如果面试官明确要求“不能修改链表”那要么在比较完后再把链表恢复回来要么就退回数组解法。这也是面试中的常见谈判点。3. 手把手实现最优解法的完整代码与边界处理3.1 链表结构定义与答题模板大多数刷题平台的 C 链表结构定义类似这样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) {} };你不需要每次手输构造函数但一定要清楚next指针可能为nullptr。所有“访问node-next”的操作前提都是node本身不为空。这道题大量涉及指针移动和反转提前做好非空判断能避免一多半的段错误。3.2 快慢指针找中点循环终止条件深挖快慢指针找中点最核心的就是循环条件的选择。不少初学者会在这直接翻车所以多写点。先看最常见的写法ListNode* slow head; ListNode* fast head; while (fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; }这个循环结束后slow指向哪里当链表长度为奇数 5slow 最终指向第 3 个节点也就是正中间节点。当链表长度为偶数 4slow 最终指向第 3 个节点也就是“后半段”的第一个节点。这个结果恰好符合我们的需求从 slow 开始就是需要反转的后半段。奇数时中间节点虽然也被划入了“后半段”但它不需要找谁比对因为它自己和自己相等把中间节点一起反转比较时右半段比左半段多走一个中心节点的位置但实际上右半段长度只比左半段多 1比如长度 5右半段反转后有 3 个节点左半段有 2 个节点多出的中心节点会单独和左半段的结尾比较等下这听着有点绕。我们实际比较时用 left 从原头走right 从反转后半头走right 的长度是 3left 的“有效需要比较的长度”也是 3不对奇数时 left 和 right 的长度其实都是 3我们拿 1-2-3-2-1 推一遍右半段从 slow 指向的 3 开始反转反转后变成 1-2-3。left 从原头走到 1-2-3-2-1。比较第 1 次 left1,right1第 2 次 left2,right2第 3 次 left3,right3right 到 nullptr停止。所以说我们实际比较了 3 次刚好把整个后半段含中心节点和左半段加中心节点比了一遍因此不能说左半段只需要比较 2 个。这里的关键是right 的长度为 (n1)/2left 从一开始也会走到相应位置两者步数相同。所以最终用 right 是否为空来控制循环逻辑成立。对于偶数长度 4slow 指向第 3 个节点反转后半 2-1 后 right 长度 2left 也需要比较前 2 个节点步数一致。所以结论while (fast ! nullptr fast-next ! nullptr)能够让我们直接从 slow 开始反转不需要额外的中点前一个节点。还有另一种循环写法while (fast-next ! nullptr fast-next-next ! nullptr)这种写法下奇数长度时 slow 指向正中间节点偶数长度时 slow 指向第一个中间节点偏左。如果使用这种写法反转应该从slow-next开始。很多题解就是这么写的。它也有道理只是后续反转起点不同。一句话总结和后面的反转逻辑必须配套不能混用。我推荐第一种写法因为它让“反转从 slow 开始”这件事更直白不容易混乱。但无论哪种一定要在纸上画出奇数和偶数两种链表自己推演一遍。3.3 反转链表迭代实现细节反转链表是链表操作的基本功直接给代码ListNode* prev nullptr; while (slow ! nullptr) { ListNode* nextNode slow-next; slow-next prev; prev slow; slow nextNode; }这里最容易犯的错误是在slow-next prev;之后立刻让slow slow-next;。这就大错特错了。因为slow-next已经被改成指向 prev原来的下一个节点早就丢了。正确做法是先用临时变量nextNode保存原来的slow-next等slow-next修改完毕后再把slow移动到nextNode。这个过程不需要额外开辟空间只用了三个指针变量。反转结束后prev就是反转后链表的头节点。为了后面比较方便可以单独用一个变量rightHead保存它例如ListNode* rightHead prev;3.4 比较阶段为什么用 right 指针判空而不是 left反转完后半段后链表变成了两条独立的链左链原链表前半段头节点是 head。右链原链表后半段反转后的结果头节点是 rightHead。比较循环常见的正确写法ListNode* left head; ListNode* right rightHead; while (right ! nullptr) { if (left-val ! right-val) { return false; } left left-next; right right-next; } return true;有人会想为什么不用left ! nullptr作为循环条件因为链表长度是奇数时右链比左链“看起来”短我们重新思考一下。假设长度为 5右链长度为 3含中心节点左链长度为 5。如果用left ! nullptr控制循环当 right 已经为空时left 还在原链表的后半段没有被反转的部分继续遍历这时候拿 left 的当前值和 right 的已访问空间nullptr做比较就会出问题。但因为我们用 right 判空循环会在右链遍历结束后自动停住左链即使还有剩余节点也不用管。换句话说右链是“有效比较长度”的标尺。另外要注意在比较前原链表后半段已经被反转所以 left 在走到原链表中心节点之后会继续沿着“旧的后半段方向”走从而可能进入一个已经被改写的区域。对于这个问题同样依赖 right 判空来规避。所以把右链判空作为循环条件是这个解法的关键细节。3.5 完整题解代码含边界处理把以上所有细节拼起来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; } // 反转后半段链表 ListNode* prev nullptr; while (slow ! nullptr) { ListNode* nextNode slow-next; slow-next prev; prev slow; slow nextNode; } // 逐个比较 ListNode* left head; ListNode* right prev; while (right ! nullptr) { if (left-val ! right-val) { return false; } left left-next; right right-next; } return true; }这段代码可以直接跑过大多数平台的测试用例。时间复杂度 O(n)空间复杂度 O(1)。唯一的影响是题目要求不允许修改原链表结构的话需要额外处理。3.6 要不要恢复链表这里给你一个明确答案这可能是这道题最有争议的细节。很多面试官会追问“你的解法修改了链表原链表还能用吗”标准做法是在比较完之后把后半段链表再反转回去恢复原结构。恢复的思路很简单既然我们在反转后半段之前并没有专门保存“中点前一个节点”但我们可以倒推。反转后原链表的结构是 head - ... - 走到原中点前一个节点后再往后就是被反转链的末尾实际上复杂一些。最简单的方式是找中点时同时记录中点前一个节点midPrev反转后半段后不要丢失。如果担心增加实现复杂度也可以在函数里用两个指针遍历记录。具体恢复时把 rightHead 指向的后半段再次反转然后接到 midPrev 后面。这段代码不复杂但会让题解长度变长。刷题平台上通常不需要恢复因为函数返回后链表就会被销毁但面试时我建议你主动问一句“需要我恢复原链表吗”这既能展示你的思考深度也能避免和面试官预期不一致。4. 实操中的高频踩坑与排查实录4.1 循环条件写错中点偏移导致结果错误我在很多地方看到有人这样写while (fast-next ! nullptr fast-next-next ! nullptr) { slow slow-next; fast fast-next-next; }如果后面跟着“从 slow 开始反转”那就错了。以偶数链表 1-2-2-1 为例用这个循环slow 最终指向第二个节点即第一个 2而真正应该反转的是从第三个节点开始的“2-1”。如果从第二个节点开始反转链表就变成了 1-(反转后变成 1-2-2-1? ) 反正比较会错。正确做法是搭配slow-next作为反转起点或者就把循环条件改成fast ! nullptr fast-next ! nullptr。怎么排查拿一个长度为 4 和长度为 5 的测试用例分别打印 slow 的位置看是否和预期一致。这一步值得做成调试习惯。4.2 反转时丢掉后继指针这是链表反转最经典的 bugwhile (slow ! nullptr) { slow-next prev; prev slow; slow slow-next; // 错误此时 slow-next 已经变成 prev }这句slow slow-next实际上让 slow 回退到了前一个节点程序大概率会死循环或者访问空指针。正确必须是ListNode* nextNode slow-next; slow-next prev; prev slow; slow nextNode;怎么排查如果程序运行后卡住或者超时优先检查是不是反转链表时丢了后继。4.3 比较阶段用错循环条件导致空指针异常有人会写while (left ! nullptr) { if (left-val ! right-val) return false; left left-next; right right-next; }这个写法在长度是偶数时可能侥幸通过但长度是奇数时right 会先变成 nullptr下一步right-val直接段错误。原因上面已经分析过right 链的长度是“有效比较长度”用它判空才成立。4.4 没有提前处理空链表和单节点最简单也最容易犯的错。如果没有if (head nullptr || head-next nullptr) return true;那么空链表执行head-next会直接崩溃单节点链表可能因为快慢指针的中点和反转逻辑产生意外结果。这两行看起来不起眼却必不可少。4.5 测试用例设计建议建议准备五组用例空链表NULL单节点1奇数长度回文1-2-3-2-1偶数长度回文1-2-2-1非回文1-2-3-1全相同节点1-1-1-1-1特别是第 3 和第 4 组能覆盖奇偶长度两种路径。跑通这六组基本可以认为解法在逻辑上没问题。5. 从这道题延伸出的链表答题方法论5.1 链表题通用的四步套路链表题做多了会发现解法往往有固定套路画图把链表结构画出来标出每一步指针变化边界优先空链表、单节点、双节点这些极端情况先确认选用合适的技巧快慢指针、反转、哑节点、合并等等用测试用例收尾奇偶长度、相同节点、重复值都要覆盖。OR36 这道题几乎完美覆盖了 1、2、3、4所以把它彻底吃透能帮你在其他链表题上少走很多弯路。5.2 双指针题型家族不止这一道快慢指针这个概念在链表题里是一整个家族环形链表判断是否有环快慢指针是否相遇环形链表起点找出环的入口节点链表的倒数第 k 个节点快指针先走 k 步再同步走链表的中点就是这个题回文链表找中点 反转如果你把这几个题放在一起刷会发现很多代码结构非常相似。刷题最忌讳一题一姿势。通过这道题把“快慢指针 反转”组合技练熟后面遇到类似问题能形成条件反射。5.3 面试时怎么表达时空权衡才加分面试官问你“还有没有更好的解法”时千万别只说“可以用快慢指针”。更优的表达节奏是先说暴力数组法代码简单空间 O(n)再优化到快慢指针 反转空间 O(1)最后主动提一句“这个做法会修改原链表。如果要求不能修改我可以在比较完后再反转回来或者使用递归法。”这么一说面试官立刻知道你不光背答案是真正理解了设计取舍。很多候选人代码写得出来却说不清楚为什么这就是失分点。5.4 手撕这道题时的推荐讲解顺序建议按照下面这个顺序向面试官展示复述题意判断链表值序列是否回文确认约束能不能修改链表是否要求空间 O(1)讲思路找中点、反转后半、两指针比较为什么能这样做开始写代码边写边解释关键步骤跑测试挑一个奇数长度回文和一个偶数长度回文手动走一遍。如果你能把“确认约束”这一步做出来就已经先赢了一半。绝大多数面试官不指望候选人第一版写出完美代码他们更看重你是否有清晰的边界意识和结构感。最后再分享一个我自己的习惯我刷链表题有个固定动作不管题目多简单都会在纸上画一条长度为 6 的链表把所有指针的移动轨迹标出来。特别是这种涉及反转的题画一遍比看十遍解析都管用。因为链表的指针变化是有“时间顺序”的一步错、步步错纸上能非常直观地看出来。OR36 这道题我前前后后写过三种解法每次写都会在“反转后判空条件”上顿一下。但当你把奇偶情况彻底琢磨清楚脑子里一旦形成“找中点→反转后半→右链判空”这条肌肉记忆这道题就不再是难题反而会变成你答链表题时的信心来源。后面再遇到类似的变种比如判断两条链表是否构成回文、回文链表的所有子序列你也能很快定位到核心考点。
链表回文这种题说实话算是链表操作里的“分水岭”。OR36这道题刷题平台上的题号记不太清但内容我闭着眼都能画出来给一条单链表判断它是不是回文结构就是说链表的节点值序列从左往右读和从右往左读是否完全一致。比如 1-2-3-2-1 就是回文1-2-2-1 也是回文而 1-2-3-1 就不是。很多新手第一次看到这题第一反应就是“这不简单嘛转成数组再用双指针从两头往中间比”。能这么做但面试官大概率会追问一句“能不能优化到 O(1) 的空间复杂度”这个时候如果你只会数组法基本就卡住了。这篇文章不打算给你灌鸡汤就老老实实把这道题从暴力到最优全部拆开数组法、递归法、快慢指针 反转后半段的最优解每一段代码都给你每一步为什么这么写、坑在哪儿也都讲明白。不管你是刚开始刷链表题的小白还是准备面试想把手撕算法练熟的选手这篇都值得看完。尤其是那些“看似对了、一跑就崩”的边界条件我会全部摊开来聊。1. 题解核心思路拆解1.1 回文链表到底在考什么回文Palindrome这个概念大家不陌生字符串、数组里判断回文非常简单左右两个指针往中间走逐个比较就行。但换到链表上问题就来了。单链表是单向的只能从头往后遍历你没办法像数组那样随机访问“倒数第几个节点”。所以这道题表面上问的是“是不是回文”实际上考的是三个链表的底层基本功怎么在单链表中找到中间节点怎么把一条链表原地反转怎么处理奇偶长度带来的边界值差异这三个点恰好覆盖了链表操作里最常见、最核心的技法。所以这道题才被很多面试官当成“试金石”题——代码量不大但考察点不少写得干净利落的人基本功基本不会差。1.2 从回文定义反推设计思路回文的本质是前半段与后半段“逆序后”相等。比如长度为 5 的链表 1-2-3-2-1前半段是 1、2后半段是 2、1把后半段反转后就是 1、2正好和前半段相等。中间那个 3 是“中心”不需要参与比较。想通这一点解决方案就呼之欲出先找到链表的中点把中点之后的节点整体反转用两个指针一个从正数第一个节点走一个从原链表尾节点反转后的新头走逐个比较如果比到最后都相等就是回文否则不是。这就是最优解的核心脉络。后面的所有代码都是围绕这条主线展开的。1.3 为什么首选快慢指针而不是先求链表长度有人可能会想既然要找中点我直接先遍历一遍求出链表长度 n然后走 n/2 步找到中点不就行了吗确实可以时间复杂度也是 O(n)代码写起来甚至更直观。但在链表题里快慢指针是更高频、更通用的技巧。它的优势在于只遍历一遍就能找到中点不需要额外维护“长度”这个变量处理环形链表、找倒数第 k 个节点等场景时同样适用。当然面试的时候如果你先讲求长度法再讲优化成快慢指针这个思路推进过程本身也是加分项。但最终给出的最优解一定是快慢指针。1.4 先想清楚空间复杂度的取舍这道题最容易被诟病的就是“用数组存值”。数组法的空间复杂度是 O(n)在数据量小的测试用例下看不出问题可一旦链表长度来到百万级额外分配一个百万长度的数组既不优雅也不靠谱。递归法虽然代码很漂亮但递归栈深度等链表长度依然是 O(n) 空间长链表还可能栈溢出。真正能达到 O(1) 空间的只有“反转后半段 双指针比较”这种做法。所以在正式讲代码前你要有一个意识解链表题和做业务需求一样先看限制条件最严的场景。如果题目没有明确说不能改链表结构那么反转后半段是性价比最高的选择。2. 从暴破到最优三种解法逐个拆解2.1 解法一复制到数组双指针往中间扫这个方法最直白。第一次遍历链表把所有节点的值按顺序塞进一个数组然后用数组双指针一头一尾往中间比较。核心代码大概是这样的以 C 为例bool isPalindromeByArray(ListNode* head) { vectorint vals; ListNode* p head; while (p ! nullptr) { vals.push_back(p-val); p p-next; } int left 0, right vals.size() - 1; while (left right) { if (vals[left] ! vals[right]) { return false; } left; --right; } return true; }这个解法的优势非常明显简单、不容易出错基本不需要考虑链表指针细节。缺点也很明显如果链表特别长数组会占用大量额外空间而且在某些面试场景下面试官会直接追加一句“不能用额外容器”那这个方法就彻底废了。需要强调的是这并不代表它“不好”。对于实际业务里那些长度可控、又不要求极低内存的场景数组解法足够可靠。刷题和面试你得学会在不同条件下切换思路。2.2 解法二递归后序遍历模拟双端比较递归解法的思路非常巧妙链表天然是线性的所以我可以先递归到最后一个节点然后在“回溯”的过程中让一个“外部指针”从头开始往前走这样一前一后就能进行比较。举个例子链表是 1-2-3-2-1递归函数一层层深入递归到节点 5值 1回溯到它时外部指针指向节点 1值 1比较相等外部指针后移继续回溯到节点 4值 2此时外部指针指向节点 2值 2比较相等继续回溯到节点 3值 3外部指针指向节点 3值 3相等之后所有回溯节点都比较完毕返回 true。C 代码一般写成这样class Solution { private: ListNode* front; public: bool check(ListNode* node) { if (node nullptr) { return true; } bool result check(node-next); // 后半部分比较已经失败的话直接短路 result result (front-val node-val); front front-next; return result; } bool isPalindromeByRecursion(ListNode* head) { front head; return check(head); } };这个解法的代码非常短但有两个致命短板递归深度等于链表长度空间复杂度是 O(n)当链表太长时递归栈会溢出程序直接崩掉。所以它更适合作为“思路展示”给面试官看不适合作为最终的线上答案。不过理解递归回溯的过程对理解树、图这类结构性数据的遍历也有帮助不妨练一练。2.3 解法三快慢指针找中点 反转后半链表现在来到正题。这个解法的精妙之处在于它把链表拆成了两半后半段原地反转然后和前半段逐个比较。整个过程只需要有限的几个指针变量空间复杂度 O(1)。先分四步走第一步处理特殊情况空链表和只有一个节点的链表天然就是回文直接返回 true。第二步用快慢指针找中点。慢指针每次走一步快指针每次走两步。当快指针到达链表尾部时慢指针正好停在中间偏右的位置上。这一步需要特别注意循环条件我在后面第 3.2 节里会专门展开。第三步从慢指针所在位置开始把后半段链表彻底反转。反转之后原本链表的尾部变成了“新后半段”的头节点。第四步用两个指针分别从原链表头和反转后的后半段头开始同步往后走逐一比较每个节点的值。只要有一对不同直接返回 false。如果后半段全部比完还没发现差异就说明是回文。这个思路不仅是这道题的答案也是很多链表题的通用套路找中点 反转 合并 / 比较。掌握它比单纯背会一道道题有用得多。2.4 三种方式对比一张表看清差距方案时间复杂度空间复杂度是否破坏原链表代码复杂度适用场景数组 双指针O(n)O(n)否极低链表较短、对空间没要求的场景递归后序比较O(n)O(n)否低思路展示、短链表快慢指针 反转后半O(n)O(1)是中面试标准答案、大型链表注意第三种方案会破坏原链表结构。后面我们来讨论这个点怎么应对。先记住如果面试官明确要求“不能修改链表”那要么在比较完后再把链表恢复回来要么就退回数组解法。这也是面试中的常见谈判点。3. 手把手实现最优解法的完整代码与边界处理3.1 链表结构定义与答题模板大多数刷题平台的 C 链表结构定义类似这样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) {} };你不需要每次手输构造函数但一定要清楚next指针可能为nullptr。所有“访问node-next”的操作前提都是node本身不为空。这道题大量涉及指针移动和反转提前做好非空判断能避免一多半的段错误。3.2 快慢指针找中点循环终止条件深挖快慢指针找中点最核心的就是循环条件的选择。不少初学者会在这直接翻车所以多写点。先看最常见的写法ListNode* slow head; ListNode* fast head; while (fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; }这个循环结束后slow指向哪里当链表长度为奇数 5slow 最终指向第 3 个节点也就是正中间节点。当链表长度为偶数 4slow 最终指向第 3 个节点也就是“后半段”的第一个节点。这个结果恰好符合我们的需求从 slow 开始就是需要反转的后半段。奇数时中间节点虽然也被划入了“后半段”但它不需要找谁比对因为它自己和自己相等把中间节点一起反转比较时右半段比左半段多走一个中心节点的位置但实际上右半段长度只比左半段多 1比如长度 5右半段反转后有 3 个节点左半段有 2 个节点多出的中心节点会单独和左半段的结尾比较等下这听着有点绕。我们实际比较时用 left 从原头走right 从反转后半头走right 的长度是 3left 的“有效需要比较的长度”也是 3不对奇数时 left 和 right 的长度其实都是 3我们拿 1-2-3-2-1 推一遍右半段从 slow 指向的 3 开始反转反转后变成 1-2-3。left 从原头走到 1-2-3-2-1。比较第 1 次 left1,right1第 2 次 left2,right2第 3 次 left3,right3right 到 nullptr停止。所以说我们实际比较了 3 次刚好把整个后半段含中心节点和左半段加中心节点比了一遍因此不能说左半段只需要比较 2 个。这里的关键是right 的长度为 (n1)/2left 从一开始也会走到相应位置两者步数相同。所以最终用 right 是否为空来控制循环逻辑成立。对于偶数长度 4slow 指向第 3 个节点反转后半 2-1 后 right 长度 2left 也需要比较前 2 个节点步数一致。所以结论while (fast ! nullptr fast-next ! nullptr)能够让我们直接从 slow 开始反转不需要额外的中点前一个节点。还有另一种循环写法while (fast-next ! nullptr fast-next-next ! nullptr)这种写法下奇数长度时 slow 指向正中间节点偶数长度时 slow 指向第一个中间节点偏左。如果使用这种写法反转应该从slow-next开始。很多题解就是这么写的。它也有道理只是后续反转起点不同。一句话总结和后面的反转逻辑必须配套不能混用。我推荐第一种写法因为它让“反转从 slow 开始”这件事更直白不容易混乱。但无论哪种一定要在纸上画出奇数和偶数两种链表自己推演一遍。3.3 反转链表迭代实现细节反转链表是链表操作的基本功直接给代码ListNode* prev nullptr; while (slow ! nullptr) { ListNode* nextNode slow-next; slow-next prev; prev slow; slow nextNode; }这里最容易犯的错误是在slow-next prev;之后立刻让slow slow-next;。这就大错特错了。因为slow-next已经被改成指向 prev原来的下一个节点早就丢了。正确做法是先用临时变量nextNode保存原来的slow-next等slow-next修改完毕后再把slow移动到nextNode。这个过程不需要额外开辟空间只用了三个指针变量。反转结束后prev就是反转后链表的头节点。为了后面比较方便可以单独用一个变量rightHead保存它例如ListNode* rightHead prev;3.4 比较阶段为什么用 right 指针判空而不是 left反转完后半段后链表变成了两条独立的链左链原链表前半段头节点是 head。右链原链表后半段反转后的结果头节点是 rightHead。比较循环常见的正确写法ListNode* left head; ListNode* right rightHead; while (right ! nullptr) { if (left-val ! right-val) { return false; } left left-next; right right-next; } return true;有人会想为什么不用left ! nullptr作为循环条件因为链表长度是奇数时右链比左链“看起来”短我们重新思考一下。假设长度为 5右链长度为 3含中心节点左链长度为 5。如果用left ! nullptr控制循环当 right 已经为空时left 还在原链表的后半段没有被反转的部分继续遍历这时候拿 left 的当前值和 right 的已访问空间nullptr做比较就会出问题。但因为我们用 right 判空循环会在右链遍历结束后自动停住左链即使还有剩余节点也不用管。换句话说右链是“有效比较长度”的标尺。另外要注意在比较前原链表后半段已经被反转所以 left 在走到原链表中心节点之后会继续沿着“旧的后半段方向”走从而可能进入一个已经被改写的区域。对于这个问题同样依赖 right 判空来规避。所以把右链判空作为循环条件是这个解法的关键细节。3.5 完整题解代码含边界处理把以上所有细节拼起来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; } // 反转后半段链表 ListNode* prev nullptr; while (slow ! nullptr) { ListNode* nextNode slow-next; slow-next prev; prev slow; slow nextNode; } // 逐个比较 ListNode* left head; ListNode* right prev; while (right ! nullptr) { if (left-val ! right-val) { return false; } left left-next; right right-next; } return true; }这段代码可以直接跑过大多数平台的测试用例。时间复杂度 O(n)空间复杂度 O(1)。唯一的影响是题目要求不允许修改原链表结构的话需要额外处理。3.6 要不要恢复链表这里给你一个明确答案这可能是这道题最有争议的细节。很多面试官会追问“你的解法修改了链表原链表还能用吗”标准做法是在比较完之后把后半段链表再反转回去恢复原结构。恢复的思路很简单既然我们在反转后半段之前并没有专门保存“中点前一个节点”但我们可以倒推。反转后原链表的结构是 head - ... - 走到原中点前一个节点后再往后就是被反转链的末尾实际上复杂一些。最简单的方式是找中点时同时记录中点前一个节点midPrev反转后半段后不要丢失。如果担心增加实现复杂度也可以在函数里用两个指针遍历记录。具体恢复时把 rightHead 指向的后半段再次反转然后接到 midPrev 后面。这段代码不复杂但会让题解长度变长。刷题平台上通常不需要恢复因为函数返回后链表就会被销毁但面试时我建议你主动问一句“需要我恢复原链表吗”这既能展示你的思考深度也能避免和面试官预期不一致。4. 实操中的高频踩坑与排查实录4.1 循环条件写错中点偏移导致结果错误我在很多地方看到有人这样写while (fast-next ! nullptr fast-next-next ! nullptr) { slow slow-next; fast fast-next-next; }如果后面跟着“从 slow 开始反转”那就错了。以偶数链表 1-2-2-1 为例用这个循环slow 最终指向第二个节点即第一个 2而真正应该反转的是从第三个节点开始的“2-1”。如果从第二个节点开始反转链表就变成了 1-(反转后变成 1-2-2-1? ) 反正比较会错。正确做法是搭配slow-next作为反转起点或者就把循环条件改成fast ! nullptr fast-next ! nullptr。怎么排查拿一个长度为 4 和长度为 5 的测试用例分别打印 slow 的位置看是否和预期一致。这一步值得做成调试习惯。4.2 反转时丢掉后继指针这是链表反转最经典的 bugwhile (slow ! nullptr) { slow-next prev; prev slow; slow slow-next; // 错误此时 slow-next 已经变成 prev }这句slow slow-next实际上让 slow 回退到了前一个节点程序大概率会死循环或者访问空指针。正确必须是ListNode* nextNode slow-next; slow-next prev; prev slow; slow nextNode;怎么排查如果程序运行后卡住或者超时优先检查是不是反转链表时丢了后继。4.3 比较阶段用错循环条件导致空指针异常有人会写while (left ! nullptr) { if (left-val ! right-val) return false; left left-next; right right-next; }这个写法在长度是偶数时可能侥幸通过但长度是奇数时right 会先变成 nullptr下一步right-val直接段错误。原因上面已经分析过right 链的长度是“有效比较长度”用它判空才成立。4.4 没有提前处理空链表和单节点最简单也最容易犯的错。如果没有if (head nullptr || head-next nullptr) return true;那么空链表执行head-next会直接崩溃单节点链表可能因为快慢指针的中点和反转逻辑产生意外结果。这两行看起来不起眼却必不可少。4.5 测试用例设计建议建议准备五组用例空链表NULL单节点1奇数长度回文1-2-3-2-1偶数长度回文1-2-2-1非回文1-2-3-1全相同节点1-1-1-1-1特别是第 3 和第 4 组能覆盖奇偶长度两种路径。跑通这六组基本可以认为解法在逻辑上没问题。5. 从这道题延伸出的链表答题方法论5.1 链表题通用的四步套路链表题做多了会发现解法往往有固定套路画图把链表结构画出来标出每一步指针变化边界优先空链表、单节点、双节点这些极端情况先确认选用合适的技巧快慢指针、反转、哑节点、合并等等用测试用例收尾奇偶长度、相同节点、重复值都要覆盖。OR36 这道题几乎完美覆盖了 1、2、3、4所以把它彻底吃透能帮你在其他链表题上少走很多弯路。5.2 双指针题型家族不止这一道快慢指针这个概念在链表题里是一整个家族环形链表判断是否有环快慢指针是否相遇环形链表起点找出环的入口节点链表的倒数第 k 个节点快指针先走 k 步再同步走链表的中点就是这个题回文链表找中点 反转如果你把这几个题放在一起刷会发现很多代码结构非常相似。刷题最忌讳一题一姿势。通过这道题把“快慢指针 反转”组合技练熟后面遇到类似问题能形成条件反射。5.3 面试时怎么表达时空权衡才加分面试官问你“还有没有更好的解法”时千万别只说“可以用快慢指针”。更优的表达节奏是先说暴力数组法代码简单空间 O(n)再优化到快慢指针 反转空间 O(1)最后主动提一句“这个做法会修改原链表。如果要求不能修改我可以在比较完后再反转回来或者使用递归法。”这么一说面试官立刻知道你不光背答案是真正理解了设计取舍。很多候选人代码写得出来却说不清楚为什么这就是失分点。5.4 手撕这道题时的推荐讲解顺序建议按照下面这个顺序向面试官展示复述题意判断链表值序列是否回文确认约束能不能修改链表是否要求空间 O(1)讲思路找中点、反转后半、两指针比较为什么能这样做开始写代码边写边解释关键步骤跑测试挑一个奇数长度回文和一个偶数长度回文手动走一遍。如果你能把“确认约束”这一步做出来就已经先赢了一半。绝大多数面试官不指望候选人第一版写出完美代码他们更看重你是否有清晰的边界意识和结构感。最后再分享一个我自己的习惯我刷链表题有个固定动作不管题目多简单都会在纸上画一条长度为 6 的链表把所有指针的移动轨迹标出来。特别是这种涉及反转的题画一遍比看十遍解析都管用。因为链表的指针变化是有“时间顺序”的一步错、步步错纸上能非常直观地看出来。OR36 这道题我前前后后写过三种解法每次写都会在“反转后判空条件”上顿一下。但当你把奇偶情况彻底琢磨清楚脑子里一旦形成“找中点→反转后半→右链判空”这条肌肉记忆这道题就不再是难题反而会变成你答链表题时的信心来源。后面再遇到类似的变种比如判断两条链表是否构成回文、回文链表的所有子序列你也能很快定位到核心考点。
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
