回文链表这道题几乎是我每次给新人讲链表相关面试题时都会第一个拿出来的例子。它表面上只是个“判断链表是否回文”的简单任务但真要在白板上写出最优解能同时覆盖链表遍历、快慢指针、原地反转、边界条件这四块硬功夫。网上讲这道题的文章很多但多数要么只贴个代码要么就是把 LeetCode 官方题解换个说法抄一遍。我这篇不打算重复那些套话而是从为什么这么解、坑在哪里、面试时怎么和面试官聊这几个角度把这道题彻底拆开顺便把我们实际工程里处理类似问题的一些习惯也带进去。事先说明本文所有思路默认基于单链表。如果面试碰到的双向链表那直接用双指针从两端往中间走就行难度直接降一档相信不需要我多讲。1. 题目到底在考什么1.1 什么是回文链表先给刚接触链表的读者一个直观定义。回文用大白话说就是“正着读和倒着读都一样”。字符串里有回文比如“level”、“上海自来水来自海上”链表里也有回文比如1 - 2 - 3 - 2 - 1这个链表正着遍历是 1 2 3 2 1倒着遍历也是 1 2 3 2 1它就是个回文链表。再看这个1 - 2 - 3 - 3 - 1正着读和倒着读不一致不是回文。题目要求很简单给定一个单链表的头节点 head判断这个链表是否是回文链表。返回值是布尔值true 或 false。LeetCode 对应的是第 234 题难度标注为“简单”但真要在面试里写出让面试官满意的解法绝对不只是“简单”两个字能概括的。很多读者可能觉得这题简单无非是“遍历一遍存下来再比较”。没错这是最直接的办法但往往不是面试官想要的答案。面试官更希望看到的是你能不能在 O(1) 额外空间复杂度下解决这个问题也就是说不借助数组、栈这些额外容器。1.2 为什么链表比数组难处理想理解这道题为什么值得单独拿出来讲先要理解链表的“反人性”之处。数组支持随机访问arr[0] 和 arr[n-1] 拿出来比一下再从两头往中间走回文判断非常简单。但链表本身是单向的每个节点只知道下一个节点是谁不知道上一个节点是谁。这意味着你想从尾部往前走根本做不到。那怎么办常规思路要么是用额外空间“记住”前面的节点比如栈要么就得换个角度把链表后半段反转过来让它暂时变成一种“能从后往前比较”的结构。这就是这道题的精髓它表面上是回文判断实际考察的是你能否灵活操作链表结构而不是只会遍历。另一个值得提的点是回文链表在真实工业场景里并不常见但它背后的技能组合是通用的。你判断回文时用到的快慢指针在很多链表类问题上都出现中途反转链表更是链表题的基本功。所以这道题本质上是把两道高频考点——找中点、反转链表——缝合在一起的综合题刷透它相当于同时复习了好几个知识点。2. 从暴力思路到最优解2.1 最容易想到的方案复制到数组再判断先说说新手最常见的思路也是很多人第一反应能写出来的解法。具体做法是第一遍遍历链表把所有节点的值按顺序存进一个数组或 ArrayList、vector。因为数组支持下标访问这时候问题就变成了普通的回文数组判断——用左指针指向下标 0右指针指向数组最后一个元素两边同时往中间走一旦发现 arr[left] ! arr[right] 就返回 false直到两指针相遇。看代码这个思路非常直白bool isPalindrome(ListNode* head) { vectorint vals; while (head) { vals.push_back(head-val); head head-next; } int left 0, right (int)vals.size() - 1; while (left right) { if (vals[left] ! vals[right]) return false; left; right--; } return true; }这个解法能正确解决问题时间复杂度 O(n)空间复杂度 O(n)。对于很多场景来说这个答案已经“能跑通了”。但如果是在面试里面试官大概率会追问一句能不能不用额外空间这时候如果你没准备就容易卡住。我第一次自己刷这道题时也是写的这个版本心里还觉得挺得意——毕竟逻辑简单、不容易出错。后来看题解才发现这道题真正考察的是空间优化也就是下面要说的双指针 反转链表法。所以如果读者时间充裕建议直接学最优解如果时间紧至少也要理解暴力思路作为兜底因为不是所有场景都要求 O(1) 空间。2.2 空间 O(1) 的核心思路拆成两半再比较要省掉额外空间核心思路可以这样理解我们想比较“前半段”和“后半段”是否对称但单链表没法从尾部开始。那不如做个转换——把后半段链表原地反转让它的头节点变成原链表的尾节点。这样一来链表从“单向不可回溯”变成了“从中间断开、两边都从头开始遍历”问题就简单多了。具体分三步走用快慢指针找到链表的中间节点。从中间节点开始把后半段链表反转。从链表头部和后半段头部同时出发逐个比较节点的值直到后半段走完。这里最关键的细节是“如何找中间节点”和“如何反转链表”。如果对这两步不够熟练后面写代码时极其容易出 bug。下面逐一展开先讲原理再给可运行代码。2.3 找中点为什么要用快慢指针找链表中间节点经典的技巧是“快慢指针”也叫“龟兔赛跑”。两个指针都从头节点出发慢指针 slow 每次走一步快指针 fast 每次走两步。当 fast 到达链表末尾时slow 刚好走到中间位置。为什么能走到中间因为 fast 的速度是 slow 的两倍同样的时间内 fast 走过的距离是 slow 的两倍。当 fast 走到 null走完整个链表时slow 走过的距离恰好是链表总长度的一半。这个逻辑非常直观和“一个人跑步速度是另一个人的两倍同时出发跑得快的人到终点时慢的人一定在中间点”是一个道理。这里有个细节需要单独拎出来说链表长度是奇数还是偶数会导致 slow 最终停顿的位置不同。链表长度为奇数时比如 1-2-3-2-1节点数是 5slow 会停在正中间节点值为 3 的位置。链表长度为偶数时比如 1-2-2-1节点数是 4slow 会停在第二个中间节点后一个值为 2 的位置。这两种情况下反转后半段的起点不一样后面写代码时要分清。我的经验是统一从 slow-next 开始反转后半段这样不管奇数偶数都能覆盖到所有应该比较的节点。原因后面代码演示时会说明。2.4 反转链表必须掌握的三指针迭代法反转链表是链表题的另一大基本功。迭代写法用三个指针prev、cur、next。核心逻辑就是循环里不断改变 cur 的 next 指向让它指向前一个节点而不是后一个节点。初始状态prev 指向 nullcur 指向头节点。每轮循环做四件事用 next 暂存 cur 的下一个节点防止断链。将 cur-next 指向 prev完成反转。将 prev 移动到 cur旧的下一个节点变成新的“前一个节点”。将 cur 移动到 next继续处理原链表的下一个节点。循环一直到 cur 为 null 为止此时 prev 恰好指向原链表的尾节点也就是反转后链表的头节点。返回 prev 即可。听上去简单但实操中新手最容易犯的错是忘了先用 next 保存下一个节点就直接修改 cur-next导致链表断掉。后面哪个节点都访问不到了。这个顺序一定不能乱。我见过太多人在白板上画了半天代码里却没有 next 这个临时变量最后整个链表变成死循环或者直接丢了一半节点面试现场翻车。3. 完整实现与代码细节3.1 把三步操作串起来的主流程前面已经把原理拆开讲了现在从整体上把主流程组装起来。完整的步骤比上面的三步要更细一些我按顺序列出处理边界情况如果链表为空或者只有一个节点直接返回 true空链表和单节点链表天然是回文。定义快慢指针 slow、fast都初始化为 head。fast 每次走两步slow 每次走一步循环条件是 fast 不为空且 fast-next 不为空。循环结束后slow 指向链表中间位置奇数或前半段的最后一个节点偶数。此时 split 指针指向 slow-next也就是后半段的起点。对 split 引导的后半段链表做反转操作得到新头节点 tail。用 p1 指向 head原链表头部p2 指向 tail反转后的后半段头部同时比较 p1 和 p2 的值不相等就返回 false否则 p1、p2 各自向后移动一步。循环条件建议写成 p2 不为空而不是 p1 不为空。因为后半段反转后p2 最多走到原链表的尾节点就结束了而 p1 可能还剩前半段的节点没走完奇数长度场景下正中间节点不会被真正比较。这里第 7 步是特别容易弄错的细节。很多第一次写这个算法的人会用 while (p1 ! nullptr) 作为循环条件结果奇数长度链表下会多比较一个节点如果正中间节点值和自身对称不影响结果但万一心态崩了逻辑绕不清楚很容易把自己绕进去。我的建议是循环条件只看后半段后半段走完就结束。3.2 可运行的参考代码下面用 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) {} }; ListNode* reverseList(ListNode* head) { ListNode* prev nullptr; ListNode* cur head; while (cur ! nullptr) { ListNode* next cur-next; // 先存下下一步要访问的节点 cur-next prev; // 反转指针方向 prev cur; // 前驱指针后移 cur next; // 当前指针后移 } return prev; } 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. split 指向后半段的起点 // 当链表长度为奇数时slow 正好在中间节点后半段从 slow-next 开始 // 当链表长度为偶数时slow 在前半段的最后一个节点后半段同样从 slow-next 开始 ListNode* split slow-next; // 3. 反转后半段链表 ListNode* tail reverseList(split); // 4. 两边从头遍历并比较 ListNode* p1 head; ListNode* p2 tail; while (p2 ! nullptr) { if (p1-val ! p2-val) { return false; } p1 p1-next; p2 p2-next; } return true; }以链表 1-2-3-2-1 为例走一遍初始 slow1fast1。第一轮slow 到 2fast 到 3。第二轮slow 到 3fast 到 2 后再走一步为 null循环结束。此时 slow 指向 3。split 指向 3 的下一个节点 2。反转 2-1 这个后半段得到 1-2 的新链表tail 指向这个新头节点值 1。p1head 为 1p2tail 为 1相等p1 到 2p2 到 2相等p2 到 null循环结束返回 true。再看 1-2-2-1 这个偶数长度例子第一轮slow 到 2第一个 2fast 到 2第二个 2。第二轮slow 到 2第二个 2fast 到 null循环结束。slow 指向前半段最后一个节点即第一个 2 的下一个节点第二个 2。split 指向这个 2 的下一个节点也就是尾节点 1。反转 1得到链表 1tail1。p1head 为 1p21相等p1 到 2p2 到 null循环结束返回 true。对比这两个例子你会发现循环条件 while (p2 ! nullptr) 天然规避了“奇数长度下正中间节点要不要比较”的纠结。因为正中间节点只有自己和自己对称比较与不比较都不影响最终结果干脆不用管它。3.3 空间复杂度和时间复杂度分析这个算法对链表进行有限次遍历每一轮操作都是常数时间所以时间复杂度是 O(n)。实际运行中找中点遍历一遍反转后半段又遍历一半比较再遍历一半总共大概走两遍完整的链表虽然常数系数略大但渐进复杂度仍然是 O(n)。面试时可以直接说 O(n)。额外空间方面只使用了几个指针变量没有用到和链表长度相关的额外存储所以空间复杂度是 O(1)。这正是面试官想听到的答案。有些人会问反转链表会不会在内存里产生新的节点不会。reverseList 只是修改节点内部的 next 指针指向节点本身还是原来那几个对象没有 new 任何新节点所以不会破坏 O(1) 空间复杂度的结论。4. 边界条件与常见错误排查实录4.1 空指针和单节点怎么处理很多新手写链表题第一步就翻车因为没有做空指针检查。空链表到底算不算回文严格来说空链表可以视为回文的真空情况但不同面试官可能有不同口径。LeetCode 上官方题解对空链表的处理是返回 true。我也建议你统一写成 true理由很简单一个链表没有任何元素正着读和倒着读都是空没有不对称的理由。这个逻辑面试官基本都认。单节点链表更不用说了1 这个链表只有一个节点当然回文。如果代码里没有这两个边界情况快慢指针那一步很可能一开始就崩溃因为 fast-next-next 这种表达式需要保证 fast 不为空、fast-next 也不为空。你当然可以通过写 while (fast fast-next) 来规避但为了逻辑清晰我一般还是会在一开头就 return。我之前在帮朋友 review 代码时就见过一个没有边界检查的版本。测试用例里有单节点链表直接段错误debug 了半小时发现是快指针访问越界。这种问题在本地一跑就能发现但在白板面试里就属于“考虑不周”的明显扣分项必须在一开始就堵住。4.2 常见错误速查表为了让大家避免踩我踩过的坑我整理了一张常见问题对照表每一行都是真实出现过的错误。错误表现根本原因正确做法程序崩了空指针异常没有判断 fast 和 fast-next 是否为空循环条件写 while (fast ! nullptr fast-next ! nullptr)判断结果错误奇偶数链表结果不对反转起点不对把中间节点也反转进了后半段统一从 slow-next 开始反转后半段死循环程序跑不完反转链表时没有用临时变量保存 next修改后丢了链表先保存 next再改 next再移动 prev 和 cur第二个节点比较时访问空指针循环条件用了 p1 ! nullptr奇数长度下多走了一次循环条件改成 p2 ! nullptr原链表被破坏无法二次使用反转后没有恢复链表结构如果面试要求不破坏原链表比较完需要再反转一次恢复结构第五行特别值得多说一句。LeetCode 234 题原本没有强制要求恢复链表原状所以网上的题解基本都不管原链表是否被破坏。但在真实工程中模块的输入输出往往有隐含约定调用方可能还需要使用这个链表。如果面试官追问“你破坏了原链表怎么办”你至少要能说出“可以再反转一次后半段恢复原状”这个方案。能主动想到这一点面试官对你的评价会明显加分。4.3 面试时如何讲清楚思路如果你在白板面试中遇到这道题可以按照“暴力解 - 优化推理 - 实现细节 - 复杂度分析 - 潜在问题”的顺序来展开。很多候选人有个误区觉得一上来直接写最优解就是最好的其实不然。面试官更看重你的思考过程以及你能否在引导下从次优解走向最优解。我的建议话术是这样先说“最直接的方法是用数组存下链表所有值然后用双指针判断时间 O(n)空间 O(n)。”然后说“但链表本身没有随机访问能力想要空间 O(1)可以考虑把后半段反转这样就能从头尾同时往中间比较。”然后补一句“找中点可以用快慢指针反转链表用三指针迭代这样总的时间复杂度还是 O(n)空间 O(1)。”最后主动提一句“这个解法会改变原链表结构如果要求不变更原链表比较结束后我可以再把后半段反转回来。”完成代码后别忘了主动说测试用例。我一般会说需要测试四类空链表、单节点、奇数长度回文、偶数长度回文以及一个非回文用例。这种系统性测试用例的思维能力在面试中非常加分。5. 从回文链表延伸出去的进阶思路5.1 递归解法优雅但不实用的另一种选择除了迭代 反转的方法回文链表还有一种递归解法。思路是用一个外部指针 left 指向链表头部然后递归遍历到链表尾部在递归返回的过程中把 left 和当前的节点逐个比较。这样相当于用递归调用栈“记住”了链表顺序然后在回溯时从尾部往头部比较。实现大概是这样的Cclass Solution { public: ListNode* left; bool traverse(ListNode* right) { if (right nullptr) return true; bool res traverse(right-next); res res (right-val left-val); left left-next; return res; } bool isPalindrome(ListNode* head) { left head; return traverse(head); } };这个解法代码很短看起来很美但代价很大递归深度等于链表长度隐式空间复杂度是 O(n)。如果链表很长还会存在递归栈溢出的风险。我自己平时很少用递归解法做这道题但在面试里如果先写出递归再优化到 O(1) 空间的迭代解法可以展示自己对递归和迭代两种范式的理解印象分会更高。5.2 同类问题一览回文数、最长回文子串、排序链表回文链表不是孤立的知识点。它会衍生出一系列相关题目刷题时建议放在一起总结。首先是 LeetCode 9回文数。输入是一个整数判断它是否是回文。这个题有两种主流做法一种是把整数转成字符串判断另一种是反转后半部分数字再比较。后者其实和回文链表的思路异曲同工都是“只处理一半然后比较前后两半”。我当年刷到这里的时候特意把两个题放在一起对比学习收获很大。其次是 LeetCode 5最长回文子串。这个题是字符串领域的经典动态规划题也可以用中心扩展法。虽然它不涉及链表但“从中间向两边扩展”的思路和回文链表中“找中点、分两半”有很强的相关性。还有一个经常和回文链表出现在同一份刷题清单里的是 LeetCode 148排序链表。它同样用到了快慢指针找中点然后把链表拆成两半再通过归并排序合并。如果你已经掌握了快慢指针找中点那么写排序链表时前半段代码几乎可以无缝迁移。把这些题横向对比你会发现一个共同模式链表问题中很多“难啃的骨头”本质上都绕不开两件事——找中点、拆链表。回文链表正是同时训练这两种能力的绝佳题目。5.3 动手练一练自己造一个测试脚手架最后给大家一个建议自己动手搭一个简单的测试脚手架不要只是复制粘贴跑 LeetCode。你可以用本地编译环境构造一个链表的辅助函数然后批量跑测试用例。这样不仅能看到输出结果还能顺手验证“链表是否被破坏”这个隐藏问题。一个简单方法是写两个辅助函数一个是根据数组创建链表一个是在调用回文判断函数后把链表再遍历一遍打印出来。比如你测试 1-2-3-2-1调用 isPalindrome 之后再遍历原链表你会发现原链表只剩前一半了因为后半段被反转并改变了指向。这能直观地帮助你理解“改变链表结构”带来的副作用。如果测试这个还原场景可以在 isPalindrome 判断完成后再把 tail 这段反转回来接回 slow-next。这样原链表结构完全不变代价只是多一次 O(n) 遍历。工程上是否值得做取决于调用方对链表后续使用的依赖程度但在面试里能主动提出并演示这点绝对是加分项。我自己在实际刷题过程中曾经反复在“奇数长度链表”上想不通——为什么 fast 到 null 时 slow 不在正中间后来我在纸上画了 5 个节点的链表一步步走完快慢指针突然就明白了slow 在节点 3是因为 fast 恰好从节点 1 跳到节点 3 再跳到空而 slow 从节点 1 走到节点 2 再走到节点 3它的位置自然就是中间。很多时候想不通不是智商问题而是动手画图的次数太少。建议读者在本地也尝试自己画图、自己推导效果比你读十篇题解都来得好。 
长河君 · 2026/9/13 8:30:51 · 阅读 1.2k 回文链表最优解：快慢指针与链表反转的实战拆解
回文链表这道题几乎是我每次给新人讲链表相关面试题时都会第一个拿出来的例子。它表面上只是个“判断链表是否回文”的简单任务但真要在白板上写出最优解能同时覆盖链表遍历、快慢指针、原地反转、边界条件这四块硬功夫。网上讲这道题的文章很多但多数要么只贴个代码要么就是把 LeetCode 官方题解换个说法抄一遍。我这篇不打算重复那些套话而是从为什么这么解、坑在哪里、面试时怎么和面试官聊这几个角度把这道题彻底拆开顺便把我们实际工程里处理类似问题的一些习惯也带进去。事先说明本文所有思路默认基于单链表。如果面试碰到的双向链表那直接用双指针从两端往中间走就行难度直接降一档相信不需要我多讲。1. 题目到底在考什么1.1 什么是回文链表先给刚接触链表的读者一个直观定义。回文用大白话说就是“正着读和倒着读都一样”。字符串里有回文比如“level”、“上海自来水来自海上”链表里也有回文比如1 - 2 - 3 - 2 - 1这个链表正着遍历是 1 2 3 2 1倒着遍历也是 1 2 3 2 1它就是个回文链表。再看这个1 - 2 - 3 - 3 - 1正着读和倒着读不一致不是回文。题目要求很简单给定一个单链表的头节点 head判断这个链表是否是回文链表。返回值是布尔值true 或 false。LeetCode 对应的是第 234 题难度标注为“简单”但真要在面试里写出让面试官满意的解法绝对不只是“简单”两个字能概括的。很多读者可能觉得这题简单无非是“遍历一遍存下来再比较”。没错这是最直接的办法但往往不是面试官想要的答案。面试官更希望看到的是你能不能在 O(1) 额外空间复杂度下解决这个问题也就是说不借助数组、栈这些额外容器。1.2 为什么链表比数组难处理想理解这道题为什么值得单独拿出来讲先要理解链表的“反人性”之处。数组支持随机访问arr[0] 和 arr[n-1] 拿出来比一下再从两头往中间走回文判断非常简单。但链表本身是单向的每个节点只知道下一个节点是谁不知道上一个节点是谁。这意味着你想从尾部往前走根本做不到。那怎么办常规思路要么是用额外空间“记住”前面的节点比如栈要么就得换个角度把链表后半段反转过来让它暂时变成一种“能从后往前比较”的结构。这就是这道题的精髓它表面上是回文判断实际考察的是你能否灵活操作链表结构而不是只会遍历。另一个值得提的点是回文链表在真实工业场景里并不常见但它背后的技能组合是通用的。你判断回文时用到的快慢指针在很多链表类问题上都出现中途反转链表更是链表题的基本功。所以这道题本质上是把两道高频考点——找中点、反转链表——缝合在一起的综合题刷透它相当于同时复习了好几个知识点。2. 从暴力思路到最优解2.1 最容易想到的方案复制到数组再判断先说说新手最常见的思路也是很多人第一反应能写出来的解法。具体做法是第一遍遍历链表把所有节点的值按顺序存进一个数组或 ArrayList、vector。因为数组支持下标访问这时候问题就变成了普通的回文数组判断——用左指针指向下标 0右指针指向数组最后一个元素两边同时往中间走一旦发现 arr[left] ! arr[right] 就返回 false直到两指针相遇。看代码这个思路非常直白bool isPalindrome(ListNode* head) { vectorint vals; while (head) { vals.push_back(head-val); head head-next; } int left 0, right (int)vals.size() - 1; while (left right) { if (vals[left] ! vals[right]) return false; left; right--; } return true; }这个解法能正确解决问题时间复杂度 O(n)空间复杂度 O(n)。对于很多场景来说这个答案已经“能跑通了”。但如果是在面试里面试官大概率会追问一句能不能不用额外空间这时候如果你没准备就容易卡住。我第一次自己刷这道题时也是写的这个版本心里还觉得挺得意——毕竟逻辑简单、不容易出错。后来看题解才发现这道题真正考察的是空间优化也就是下面要说的双指针 反转链表法。所以如果读者时间充裕建议直接学最优解如果时间紧至少也要理解暴力思路作为兜底因为不是所有场景都要求 O(1) 空间。2.2 空间 O(1) 的核心思路拆成两半再比较要省掉额外空间核心思路可以这样理解我们想比较“前半段”和“后半段”是否对称但单链表没法从尾部开始。那不如做个转换——把后半段链表原地反转让它的头节点变成原链表的尾节点。这样一来链表从“单向不可回溯”变成了“从中间断开、两边都从头开始遍历”问题就简单多了。具体分三步走用快慢指针找到链表的中间节点。从中间节点开始把后半段链表反转。从链表头部和后半段头部同时出发逐个比较节点的值直到后半段走完。这里最关键的细节是“如何找中间节点”和“如何反转链表”。如果对这两步不够熟练后面写代码时极其容易出 bug。下面逐一展开先讲原理再给可运行代码。2.3 找中点为什么要用快慢指针找链表中间节点经典的技巧是“快慢指针”也叫“龟兔赛跑”。两个指针都从头节点出发慢指针 slow 每次走一步快指针 fast 每次走两步。当 fast 到达链表末尾时slow 刚好走到中间位置。为什么能走到中间因为 fast 的速度是 slow 的两倍同样的时间内 fast 走过的距离是 slow 的两倍。当 fast 走到 null走完整个链表时slow 走过的距离恰好是链表总长度的一半。这个逻辑非常直观和“一个人跑步速度是另一个人的两倍同时出发跑得快的人到终点时慢的人一定在中间点”是一个道理。这里有个细节需要单独拎出来说链表长度是奇数还是偶数会导致 slow 最终停顿的位置不同。链表长度为奇数时比如 1-2-3-2-1节点数是 5slow 会停在正中间节点值为 3 的位置。链表长度为偶数时比如 1-2-2-1节点数是 4slow 会停在第二个中间节点后一个值为 2 的位置。这两种情况下反转后半段的起点不一样后面写代码时要分清。我的经验是统一从 slow-next 开始反转后半段这样不管奇数偶数都能覆盖到所有应该比较的节点。原因后面代码演示时会说明。2.4 反转链表必须掌握的三指针迭代法反转链表是链表题的另一大基本功。迭代写法用三个指针prev、cur、next。核心逻辑就是循环里不断改变 cur 的 next 指向让它指向前一个节点而不是后一个节点。初始状态prev 指向 nullcur 指向头节点。每轮循环做四件事用 next 暂存 cur 的下一个节点防止断链。将 cur-next 指向 prev完成反转。将 prev 移动到 cur旧的下一个节点变成新的“前一个节点”。将 cur 移动到 next继续处理原链表的下一个节点。循环一直到 cur 为 null 为止此时 prev 恰好指向原链表的尾节点也就是反转后链表的头节点。返回 prev 即可。听上去简单但实操中新手最容易犯的错是忘了先用 next 保存下一个节点就直接修改 cur-next导致链表断掉。后面哪个节点都访问不到了。这个顺序一定不能乱。我见过太多人在白板上画了半天代码里却没有 next 这个临时变量最后整个链表变成死循环或者直接丢了一半节点面试现场翻车。3. 完整实现与代码细节3.1 把三步操作串起来的主流程前面已经把原理拆开讲了现在从整体上把主流程组装起来。完整的步骤比上面的三步要更细一些我按顺序列出处理边界情况如果链表为空或者只有一个节点直接返回 true空链表和单节点链表天然是回文。定义快慢指针 slow、fast都初始化为 head。fast 每次走两步slow 每次走一步循环条件是 fast 不为空且 fast-next 不为空。循环结束后slow 指向链表中间位置奇数或前半段的最后一个节点偶数。此时 split 指针指向 slow-next也就是后半段的起点。对 split 引导的后半段链表做反转操作得到新头节点 tail。用 p1 指向 head原链表头部p2 指向 tail反转后的后半段头部同时比较 p1 和 p2 的值不相等就返回 false否则 p1、p2 各自向后移动一步。循环条件建议写成 p2 不为空而不是 p1 不为空。因为后半段反转后p2 最多走到原链表的尾节点就结束了而 p1 可能还剩前半段的节点没走完奇数长度场景下正中间节点不会被真正比较。这里第 7 步是特别容易弄错的细节。很多第一次写这个算法的人会用 while (p1 ! nullptr) 作为循环条件结果奇数长度链表下会多比较一个节点如果正中间节点值和自身对称不影响结果但万一心态崩了逻辑绕不清楚很容易把自己绕进去。我的建议是循环条件只看后半段后半段走完就结束。3.2 可运行的参考代码下面用 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) {} }; ListNode* reverseList(ListNode* head) { ListNode* prev nullptr; ListNode* cur head; while (cur ! nullptr) { ListNode* next cur-next; // 先存下下一步要访问的节点 cur-next prev; // 反转指针方向 prev cur; // 前驱指针后移 cur next; // 当前指针后移 } return prev; } 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. split 指向后半段的起点 // 当链表长度为奇数时slow 正好在中间节点后半段从 slow-next 开始 // 当链表长度为偶数时slow 在前半段的最后一个节点后半段同样从 slow-next 开始 ListNode* split slow-next; // 3. 反转后半段链表 ListNode* tail reverseList(split); // 4. 两边从头遍历并比较 ListNode* p1 head; ListNode* p2 tail; while (p2 ! nullptr) { if (p1-val ! p2-val) { return false; } p1 p1-next; p2 p2-next; } return true; }以链表 1-2-3-2-1 为例走一遍初始 slow1fast1。第一轮slow 到 2fast 到 3。第二轮slow 到 3fast 到 2 后再走一步为 null循环结束。此时 slow 指向 3。split 指向 3 的下一个节点 2。反转 2-1 这个后半段得到 1-2 的新链表tail 指向这个新头节点值 1。p1head 为 1p2tail 为 1相等p1 到 2p2 到 2相等p2 到 null循环结束返回 true。再看 1-2-2-1 这个偶数长度例子第一轮slow 到 2第一个 2fast 到 2第二个 2。第二轮slow 到 2第二个 2fast 到 null循环结束。slow 指向前半段最后一个节点即第一个 2 的下一个节点第二个 2。split 指向这个 2 的下一个节点也就是尾节点 1。反转 1得到链表 1tail1。p1head 为 1p21相等p1 到 2p2 到 null循环结束返回 true。对比这两个例子你会发现循环条件 while (p2 ! nullptr) 天然规避了“奇数长度下正中间节点要不要比较”的纠结。因为正中间节点只有自己和自己对称比较与不比较都不影响最终结果干脆不用管它。3.3 空间复杂度和时间复杂度分析这个算法对链表进行有限次遍历每一轮操作都是常数时间所以时间复杂度是 O(n)。实际运行中找中点遍历一遍反转后半段又遍历一半比较再遍历一半总共大概走两遍完整的链表虽然常数系数略大但渐进复杂度仍然是 O(n)。面试时可以直接说 O(n)。额外空间方面只使用了几个指针变量没有用到和链表长度相关的额外存储所以空间复杂度是 O(1)。这正是面试官想听到的答案。有些人会问反转链表会不会在内存里产生新的节点不会。reverseList 只是修改节点内部的 next 指针指向节点本身还是原来那几个对象没有 new 任何新节点所以不会破坏 O(1) 空间复杂度的结论。4. 边界条件与常见错误排查实录4.1 空指针和单节点怎么处理很多新手写链表题第一步就翻车因为没有做空指针检查。空链表到底算不算回文严格来说空链表可以视为回文的真空情况但不同面试官可能有不同口径。LeetCode 上官方题解对空链表的处理是返回 true。我也建议你统一写成 true理由很简单一个链表没有任何元素正着读和倒着读都是空没有不对称的理由。这个逻辑面试官基本都认。单节点链表更不用说了1 这个链表只有一个节点当然回文。如果代码里没有这两个边界情况快慢指针那一步很可能一开始就崩溃因为 fast-next-next 这种表达式需要保证 fast 不为空、fast-next 也不为空。你当然可以通过写 while (fast fast-next) 来规避但为了逻辑清晰我一般还是会在一开头就 return。我之前在帮朋友 review 代码时就见过一个没有边界检查的版本。测试用例里有单节点链表直接段错误debug 了半小时发现是快指针访问越界。这种问题在本地一跑就能发现但在白板面试里就属于“考虑不周”的明显扣分项必须在一开始就堵住。4.2 常见错误速查表为了让大家避免踩我踩过的坑我整理了一张常见问题对照表每一行都是真实出现过的错误。错误表现根本原因正确做法程序崩了空指针异常没有判断 fast 和 fast-next 是否为空循环条件写 while (fast ! nullptr fast-next ! nullptr)判断结果错误奇偶数链表结果不对反转起点不对把中间节点也反转进了后半段统一从 slow-next 开始反转后半段死循环程序跑不完反转链表时没有用临时变量保存 next修改后丢了链表先保存 next再改 next再移动 prev 和 cur第二个节点比较时访问空指针循环条件用了 p1 ! nullptr奇数长度下多走了一次循环条件改成 p2 ! nullptr原链表被破坏无法二次使用反转后没有恢复链表结构如果面试要求不破坏原链表比较完需要再反转一次恢复结构第五行特别值得多说一句。LeetCode 234 题原本没有强制要求恢复链表原状所以网上的题解基本都不管原链表是否被破坏。但在真实工程中模块的输入输出往往有隐含约定调用方可能还需要使用这个链表。如果面试官追问“你破坏了原链表怎么办”你至少要能说出“可以再反转一次后半段恢复原状”这个方案。能主动想到这一点面试官对你的评价会明显加分。4.3 面试时如何讲清楚思路如果你在白板面试中遇到这道题可以按照“暴力解 - 优化推理 - 实现细节 - 复杂度分析 - 潜在问题”的顺序来展开。很多候选人有个误区觉得一上来直接写最优解就是最好的其实不然。面试官更看重你的思考过程以及你能否在引导下从次优解走向最优解。我的建议话术是这样先说“最直接的方法是用数组存下链表所有值然后用双指针判断时间 O(n)空间 O(n)。”然后说“但链表本身没有随机访问能力想要空间 O(1)可以考虑把后半段反转这样就能从头尾同时往中间比较。”然后补一句“找中点可以用快慢指针反转链表用三指针迭代这样总的时间复杂度还是 O(n)空间 O(1)。”最后主动提一句“这个解法会改变原链表结构如果要求不变更原链表比较结束后我可以再把后半段反转回来。”完成代码后别忘了主动说测试用例。我一般会说需要测试四类空链表、单节点、奇数长度回文、偶数长度回文以及一个非回文用例。这种系统性测试用例的思维能力在面试中非常加分。5. 从回文链表延伸出去的进阶思路5.1 递归解法优雅但不实用的另一种选择除了迭代 反转的方法回文链表还有一种递归解法。思路是用一个外部指针 left 指向链表头部然后递归遍历到链表尾部在递归返回的过程中把 left 和当前的节点逐个比较。这样相当于用递归调用栈“记住”了链表顺序然后在回溯时从尾部往头部比较。实现大概是这样的Cclass Solution { public: ListNode* left; bool traverse(ListNode* right) { if (right nullptr) return true; bool res traverse(right-next); res res (right-val left-val); left left-next; return res; } bool isPalindrome(ListNode* head) { left head; return traverse(head); } };这个解法代码很短看起来很美但代价很大递归深度等于链表长度隐式空间复杂度是 O(n)。如果链表很长还会存在递归栈溢出的风险。我自己平时很少用递归解法做这道题但在面试里如果先写出递归再优化到 O(1) 空间的迭代解法可以展示自己对递归和迭代两种范式的理解印象分会更高。5.2 同类问题一览回文数、最长回文子串、排序链表回文链表不是孤立的知识点。它会衍生出一系列相关题目刷题时建议放在一起总结。首先是 LeetCode 9回文数。输入是一个整数判断它是否是回文。这个题有两种主流做法一种是把整数转成字符串判断另一种是反转后半部分数字再比较。后者其实和回文链表的思路异曲同工都是“只处理一半然后比较前后两半”。我当年刷到这里的时候特意把两个题放在一起对比学习收获很大。其次是 LeetCode 5最长回文子串。这个题是字符串领域的经典动态规划题也可以用中心扩展法。虽然它不涉及链表但“从中间向两边扩展”的思路和回文链表中“找中点、分两半”有很强的相关性。还有一个经常和回文链表出现在同一份刷题清单里的是 LeetCode 148排序链表。它同样用到了快慢指针找中点然后把链表拆成两半再通过归并排序合并。如果你已经掌握了快慢指针找中点那么写排序链表时前半段代码几乎可以无缝迁移。把这些题横向对比你会发现一个共同模式链表问题中很多“难啃的骨头”本质上都绕不开两件事——找中点、拆链表。回文链表正是同时训练这两种能力的绝佳题目。5.3 动手练一练自己造一个测试脚手架最后给大家一个建议自己动手搭一个简单的测试脚手架不要只是复制粘贴跑 LeetCode。你可以用本地编译环境构造一个链表的辅助函数然后批量跑测试用例。这样不仅能看到输出结果还能顺手验证“链表是否被破坏”这个隐藏问题。一个简单方法是写两个辅助函数一个是根据数组创建链表一个是在调用回文判断函数后把链表再遍历一遍打印出来。比如你测试 1-2-3-2-1调用 isPalindrome 之后再遍历原链表你会发现原链表只剩前一半了因为后半段被反转并改变了指向。这能直观地帮助你理解“改变链表结构”带来的副作用。如果测试这个还原场景可以在 isPalindrome 判断完成后再把 tail 这段反转回来接回 slow-next。这样原链表结构完全不变代价只是多一次 O(n) 遍历。工程上是否值得做取决于调用方对链表后续使用的依赖程度但在面试里能主动提出并演示这点绝对是加分项。我自己在实际刷题过程中曾经反复在“奇数长度链表”上想不通——为什么 fast 到 null 时 slow 不在正中间后来我在纸上画了 5 个节点的链表一步步走完快慢指针突然就明白了slow 在节点 3是因为 fast 恰好从节点 1 跳到节点 3 再跳到空而 slow 从节点 1 走到节点 2 再走到节点 3它的位置自然就是中间。很多时候想不通不是智商问题而是动手画图的次数太少。建议读者在本地也尝试自己画图、自己推导效果比你读十篇题解都来得好。