刷题群里有个同学前两天被牛客BM13“教训”了一下他第一遍用数组转存的写法秒过了结果模拟面试时对面追问“空间复杂度能不能优化到 O(1)”他直接卡住最后支支吾吾说了个“用两个指针”自己都没讲明白。这题其实非常典型——判断一个链表是否为回文结构本质上考察的不是你怎么判断“对称”而是你在一个没有反向遍历能力的单向链表上怎么模拟出“从尾往头读”的效果。下面我按自己刷题和陪练时的经验把数组快照、栈、快慢指针加反转后半段这几条路全部拆一遍重点讲清楚面试官真正想看的 O(1) 空间解法以及代码里最容易被忽略的坑。1. 先看清楚题回文结构在链表上到底卡在哪一步1.1 什么是链表回文结构回文结构就是正着读和倒着读完全一致。放到链表场景里一串节点从头到尾的值序列和从尾到头读一遍完全相同那这个链表就是回文结构。举几个直观的例子链表结果1 - 2 - 2 - 1true1 - 2 - 3 - 2 - 1true1 - 2 - 3false1 - 2 - 1 - 2false偶数长度的回文是左右两半完全对称奇数长度的回文是中间那个节点“自己和自己对称”。所以判断回文这件事拆到最底层就是不断比较两个对称位置上的节点值是否相等直到中间相遇。这个定义看起来人畜无害但放在链表上就完全不是那回事了。数组里比较两个对称位置只需要两个下标一个从左边往右一个从右边往左随机访问随手就来。链表可没这个本事你想知道中间某个节点的值必须从头节点一步一步走你想从尾巴往头走对不起单向链表根本没有 prev 指针。这道题的所有难度都集中在“怎么在没有反向遍历能力的结构上模拟出对称比较”。1.2 单向性带来的限制链表和数组最大的区别就是它只给你一条通道从 head 开始一路 next 往下走。你没法按下标定位也没法从后往前。这就导致判断回文最直观的“两端向中间靠拢”思路在链表上没法直接落地。理解这一点很重要。很多人一上来就转数组本质上是把链表强行“降维”成数组然后用数组的优势去解题。笔试阶段这样做没问题但面试官心里真正期待的是你能不能用链表本身的特性在没有额外大空间的情况下完成比较。也就是说这题考的不是“你会不会判断对称”而是“你在单向链表的限制下能不能设计出一套方案完成对称匹配”。换句生活化的比喻数组是一排带编号的格子你随手就能抽中间那张链表是一列只有箭头指向下一格的火柴盒你想倒着看要么把整个队伍的方向反过来要么用额外的工具把顺序记下来。1.3 边界条件空链表、单节点、奇偶长度链表题的边界条件通常比普通数组题更容易埋雷这题也不例外。面试官特别喜欢在边界上做文章。空链表按惯例返回 true因为没有任何不对称的可能。单节点链表只有一个节点天然回文返回 true。偶数长度比如 1 - 2 - 2 - 1需要精确定位后半段起点。奇数长度比如 1 - 2 - 3 - 2 - 1中间节点 3 是自己和自己比不影响结果但会影响指针位置的选择。全等值链表1 - 1 - 1 也是回文别因为“所有值一样”就下意识觉得不对。很多新手在奇数长度上翻车慢指针停的位置如果偏左或偏右后半段范围就错了最终比较结果就会错。所以不管用哪种解法先把这些边界在脑子里过一遍再动手写代码。2. 暴力保分方案数组快照和栈逆序笔试先拿分再说2.1 数组快照法最简单也最不容易错思路一句话遍历一次链表把所有节点值按顺序存进一个数组然后用两个下标从两端向中间比较。bool isPalindromeByArray(ListNode* head) { vectorint vals; ListNode* p head; while (p ! nullptr) { vals.push_back(p-val); p p-next; } int left 0; int right (int)vals.size() - 1; while (left right) { if (vals[left] ! vals[right]) { return false; } left; --right; } return true; }这个方法的时间复杂度是 O(n)空间复杂度是 O(n)。它的优点在于逻辑极其直白先收集数据再双指针比较。边界也不容易出错——数组长度能直接获得左下标和右下标怎么移动都是标准操作。笔试时如果时间紧张我建议直接先写这种解法保底。绝大多数 OJ 判题并不会把空间限制卡得很死数组快照法基本都能过。但这个解法最大的问题也藏在这里它完全没有利用链表的结构而是把链表先“拷贝”成了另一种数据结构。面试官一旦追问“能不能不用额外数组”你就需要拿出后面的方案。2.2 栈法天然解决“从尾到头”的问题栈是另一种很容易想到的方案而且从直觉上更贴合“回文”这个概念。栈是后进先出的你遍历链表把所有节点值依次压入栈中再把链表从头走一遍每次和栈顶比较。栈顶弹出的顺序正好是链表从尾到头的顺序。bool isPalindromeByStack(ListNode* head) { stackint st; ListNode* p head; while (p ! nullptr) { st.push(p-val); p p-next; } p head; while (p ! nullptr) { if (p-val ! st.top()) { return false; } st.pop(); p p-next; } return true; }栈法还可以优化结合快慢指针只把链表前半部分压入栈慢指针到达中点后开始弹栈和后半段节点比较。这样额外空间大约减半但量级仍然是 O(n)。优化后的代码会稍微复杂一点需要处理奇数长度的“跳过中间节点”问题bool isPalindromeByHalfStack(ListNode* head) { if (head nullptr || head-next nullptr) { return true; } ListNode* slow head; ListNode* fast head; stackint st; while (fast ! nullptr fast-next ! nullptr) { st.push(slow-val); slow slow-next; fast fast-next-next; } // 如果是奇数个节点fast 最终不为空slow 停在中间节点 if (fast ! nullptr) { slow slow-next; } while (slow ! nullptr) { if (st.top() ! slow-val) { return false; } st.pop(); slow slow-next; } return true; }再说一遍栈法的时间是 O(n)空间也是 O(n)。它比数组法省心的地方在于不需要先知道链表长度也不用维护左右下标比较过程就是“弹栈和遍历同步走”。2.3 笔试策略能 AC 的解法也是好解法很多刷题的人有一个误区总觉得暴力解拿不出手非要一步写出最优解。我的观点是笔试和面试要分开对待。笔试环境时间紧、心态容易崩这时候最怕的不是算法不够优而是你想了半天最优解没写完反而连基础分都没拿到。数组快照或栈法虽然空间是 O(n)但正确性高、实现速度快属于“保底分”。如果笔试平台本身不限制额外内存那直接用暴力法抢时间完全合理。面试就不一样了。面试官更看重的是优化路径你最好能完整展示“暴力解 - 栈优化 - O(1) 空间解”的推进过程。这也是为什么下面这个方案才是整道题的主菜。3. O(1)空间的正解快慢指针 后半段反转3.1 整体思路找一个中点翻转一半O(1) 空间解法的核心思路特别直接既然单向链表不能从后往前走那就把后半段就地反转让它变成一条从尾到头的链表。这样一来前半段保持原序后半段变成反序你从两段的头部各拿一个指针同步走正好每次比较的都是一对对称节点。整个过程可以拆成三步用快慢指针找到链表中点。从中点开始反转后半段链表。一个指针从 head 出发另一个指针从反转后的右段头出发同步比较节点值。这个思路的巧妙之处在于它没有复制任何数据只是原地改了后半段指针的方向所以额外空间只需要几个临时指针是 O(1)。代价是它修改了原链表的结构。3.2 快慢指针为什么能找到中点快慢指针找中点的原理很好理解快指针每次走两步慢指针每次走一步。当快指针到达链表末尾时慢指针刚好走完一半路程。用一个例子推演偶数链表 1 - 2 - 3 - 4快指针从 1 出发两步到 3再两步到 nullptr慢指针此时走到 3正好是后半段的起点。奇数链表 1 - 2 - 3 - 4 - 5快指针最终停在 5慢指针停在 3也就是中间节点。代码模板长这样ListNode* slow head; ListNode* fast head; while (fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; }这个 while 条件是我特别想强调的点必须先判断 fast 不为空再判断 fast-next 不为空。常见错误是写成while (fast-next fast-next-next)当链表长度很短或者快指针已经走到末尾时这个表达式可能直接对空指针解引用。每次写链表题我都建议把“防空指针”当成第一反应。3.3 反转后半段的三指针模板单链表反转是链表题的基本功很多题都会用到模板必须烂熟于心。核心逻辑就三句话ListNode* prev nullptr; ListNode* cur slow; while (cur ! nullptr) { ListNode* nxt cur-next; // 1. 先保存后继 cur-next prev; // 2. 反转指针方向 prev cur; // 3. 整体后移 cur nxt; }这里最容易犯的错就是丢掉nxt。你想让cur-next指向前驱节点但如果不在第一步保存原来的后继那cur后面的整段链表就全部失联了。这个错误几乎每个写反转链表的初学者都犯过一次我自己的经验是写完三指针循环后先在草稿纸上画三个节点推演一遍确认指针没有断再继续往下写。3.4 比较阶段中间节点其实可以“放着不管”反转后半段之后链表被分成了两段左段从原 head 出发保持原序。右段从反转后的右段头出发顺序是原链表的逆序。比较时左指针从左段头开始右指针从右段头开始同步前进。循环终止条件用while (right ! nullptr)是最稳的因为右段的长度不会超过左段加一而右段也不会像左段那样提前走到空。关于奇数长度的中间节点有一个非常容易产生困惑的细节我多说几句。当链表是奇数个节点时反转后半段会包含中间节点。比如 1 - 2 - 3 - 2 - 1找中点停在 3反转后半段后变成 1 - 2 - 3 和 1 - 2 - 3后半段反转后为 1 - 2 - 3。比较时左指针走到 3 的时候右指针也走到 3这其实是在拿中间节点和自己比较必然相等。所以你不必做任何特殊处理直接让循环跑完就行。如果要跳过中间节点也是可以的在反转前让慢指针多做一次slow slow-next但这样会引入更多边界判断反而容易出错。我实际写代码时更倾向于不做跳过让中间节点“自己和自己比”代码更简洁。ListNode* left head; ListNode* right prev; // prev 是反转后的右段头 bool result true; while (right ! nullptr) { if (left-val ! right-val) { result false; break; } left left-next; right right-next; }3.5 恢复原链表比很多人想的简单刚才提到反转后半段会修改原链表结构。牛客 BM13 和多数刷题平台并没有要求不能修改原链表所以很多题解直接不恢复。但面试时如果你能主动提出“我可以把链表恢复回去”这是一个非常加分的工程意识。恢复的思路出人意料地简单把刚才反转过的后半段再反转一次让后半段回到原来的方向。关键点在于一个容易被忽略的事实找中点的时候前半段最后一个节点的 next 指针始终指向那个中间节点这个指针从头到尾没有被改过。所以你只要把后半段反转回来让中间节点的 next 恢复成原来的后继整条链表就会自动重新接上。ListNode* tail nullptr; cur prev; // prev 仍然指向反转后的右段头注意别用已经被移动过的 right 游标 while (cur ! nullptr) { ListNode* nxt cur-next; cur-next tail; tail cur; cur nxt; }这段恢复代码不能反过来用right因为比较阶段结束之后right已经走到空了。你需要另存一份右段头引用比如上面的prev或者在最开始就把反转后的头单独存下来。4. 代码粒度级复盘C实现和四个一写就崩的细节4.1 完整参考实现综合上面的思路我给出一个带恢复逻辑的完整 C 实现。注释里标明了哪一步是可以按需裁剪的。class Solution { public: bool isPalindrome(ListNode* head) { if (head nullptr || head-next nullptr) { return true; } // 1. 快慢指针找中点 ListNode* slow head; ListNode* fast head; while (fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; } // 2. 反转后半段从 slow 开始 ListNode* prev nullptr; ListNode* cur slow; while (cur ! nullptr) { ListNode* nxt cur-next; cur-next prev; prev cur; cur nxt; } // 此时 prev 是反转后的右段头 // 3. 同步比较 ListNode* left head; ListNode* right prev; bool result true; while (right ! nullptr) { if (left-val ! right-val) { result false; break; } left left-next; right right-next; } // 4. 恢复后半段如题目要求不修改原链表则保留这段否则可省略 ListNode* tail nullptr; cur prev; while (cur ! nullptr) { ListNode* nxt cur-next; cur-next tail; tail cur; cur nxt; } return result; } };再看一个简洁的 Python 版本适合快速刷题时参考省略了恢复逻辑class Solution: def isPalindrome(self, head: ListNode) - bool: if not head or not head.next: return True slow fast head while fast and fast.next: slow slow.next fast fast.next.next prev None cur slow while cur: nxt cur.next cur.next prev prev cur cur nxt left, right head, prev while right: if left.val ! right.val: return False left left.next right right.next return True两个版本的核心逻辑完全一致。差别只在于 C 版里我保留了恢复链表的步骤Python 版则只关心判断结果。4.2 四个高频翻车位置我陪练时见过很多人在这几个位置上反复出错这里单独列出来每个都是真实案例。第一个快慢指针的循环条件写错。典型错误是写成while (fast-next fast-next-next)。如果链表只有两个节点fast 指向第二个节点时fast-next已经为空但你的条件会先判断fast-next是否为空好在这种写法在空指针上会直接崩溃。更隐蔽的错误是写成while (fast)快指针走到空之后仍然继续循环导致fast-next对空指针解引用。标准写法就是while (fast ! nullptr fast-next ! nullptr)顺序不能反。第二个反转链表时丢了后继节点。这个错我在前面已经强调过。一定要先执行ListNode* nxt cur-next再执行cur-next prev。如果你把这两句顺序写反下一次循环时cur已经找不到原来的下一个节点后半段就全丢了程序会陷入死循环或输出错误结果。画图推演是解决这个问题的最好方法。第三个比较循环用错了终止条件。有些人习惯写while (left ! nullptr)或while (left ! nullptr right ! nullptr)。在回文场景下偶数链表两边同时走到空没问题但奇数链表比较到中间节点时right 比 left 多走一步如果你用while (left)作为条件left 先变成空你还在循环内部访问left-val直接越界。统一用while (right ! nullptr)是最保险的做法因为右段要么和左段同长要么多一个中间节点用它做终止条件天然安全。第四个恢复链表时用了已经被移动的游标。比较结束后right这个游标已经走到了 nullptr如果你在恢复阶段写cur right那你反转的就是一条空链表原链表后半段根本没被恢复。正确做法是恢复阶段从prev重新开始或者在反转后半段之后把右段头单独备份一份。这类错误不好定位因为程序不一定会崩溃只是链表被改乱了。4.3 构造测试用例四组用例一口气自测链表题的正确性很大程度上靠测试用例兜底。我建议手写一个从数组建链表的辅助函数然后用下面四组用例测试ListNode* createList(initializer_listint values) { ListNode dummy(0); ListNode* tail dummy; for (int v : values) { tail-next new ListNode(v); tail tail-next; } return dummy.next; }测试清单空链表和单节点链表nullptr、createList({1})都应当返回 true。偶数回文createList({1, 2, 2, 1})返回 true。奇数回文createList({1, 2, 3, 2, 1})返回 true。迷惑用例createList({1, 2, 1, 2})返回 false。第四组很值得测。它的前半段 1、2 和后半段 1、2 看似对称但实际上你要比较的是第 1 个和第 4 个第 2 个和第 3 个也就是 1 对 2、2 对 1全不相等结果是 false。很多人粗看会以为它是回文实际不是。这类用例可以快速验证你的比较逻辑是不是真的按对称位置走的。4.4 复杂度与“破坏性”选择三种主流解法放在一起对比如下解法时间复杂度空间复杂度是否修改原链表数组快照法O(n)O(n)否栈法O(n)O(n)否快慢指针 反转后半段O(n)O(1)是但可恢复笔试时如果只想快速过题用数组法完全可行面试时建议使用快慢指针加反转的方案并且主动提“我可以把链表恢复回去”。O(1) 空间这个点往往是面试官判断你算法功底是否扎实的分水岭。5. 举一反三从回文题解锁链表算法的通用思维5.1 快慢指针的兄弟场景链表题里的双指针技巧是一个庞大的家族回文判断只是其中之一。同样的“快慢指针”模板还能直接解决下面几类高频题判断环形链表快慢指针同时出发如果某一刻两者相遇说明链表存在环。寻找链表的倒数第 K 个节点快指针先走 K 步再和慢指针同步走快指针到尾部时慢指针正好在倒数第 K 位。重排链表先找中点反转后半段再交替合并两条链表。这一步几乎是回文判断的孪生兄弟。你会发现BM13 一道题同时覆盖了“找中点”和“反转链表”两个最高频的链表基本功。练熟这一道相当于把三类题目的核心思路都过了一遍。5.2 回文判断的常见变体题目稍微变一下就又是新题但核心思路基本相通。比如“删除一个节点后能否成为回文”你可以先正常用双指针找第一处不对称的位置然后分别尝试跳过左侧节点或右侧节点再继续比较剩余部分。本质还是对称匹配只是多了一个“容忍一次失配”的条件。再比如双向链表判断回文因为它有 prev 指针你可以直接从头和尾两个方向往中间走比单向链表简单很多不需要反转任何东西。这个对比刚好能帮助你理解单向链表判断回文的难点就在于“缺一条反向走的路”。又比如判断字符串回文双指针从两端向中间走是最直接的做法和数组快照法里的比较逻辑完全一样。5.3 面试怎么把这题讲出加分感我陪练面试时总结了一个比较有效的叙述顺序先承认最直觉的解法是转数组指出空间是 O(n)再提出栈可以模拟逆序读取最后推出 O(1) 空间的快慢指针加反转方案。每一步都点出上一步的瓶颈面试官就能很清晰地看到你的思维路径。写代码之前先口头宣告三步走找中点、反转后半段、双指针同步比较。写的时候不用太急把反转链表的三指针逻辑写在纸上确认一遍。写完以后主动说一句“如果调用方要求链表保持不变我可以在比较完之后把反转过的部分再恢复回去”这句话在面试里很加分因为它说明你不只是在背题解而是考虑到了原链表被破坏这个实际工程隐患。我自己的习惯是链表题写完以后不急着提交先在心里把四个边界跑一遍空链表、单节点、偶数回文、奇数回文。这一步真的能拦住一半以上的低级错误。回文判断这道题代码量不大但信息密度非常高。它逼着你去思考单向链表的遍历限制也逼着你去熟练两个最常用的链表操作。把 BM13 吃透比你泛泛刷十几道简单链表题更有价值。下次再遇到什么分割链表、重排链表你会发现自己不再需要从头想思路——这些解法之间的联系早就串在一起了。