day130 这个标题懂的都懂——又是一天的 LeetCode 打卡。链表这一块的题反转链表LeetCode-206绝对是吞金兽般的存在。你以为你懂了一动手就 bug 满天飞你以为你已经滚瓜烂熟了面试官换个问法立刻卡壳。我今天就把这道题从原理到实现从迭代到递归从标准解法到进阶变形一次说清楚。这道题之所以值得写是因为它是整个链表类算法题的基石。反转链表你会不会写直接决定了你后面能不能搞定反转前 N 个节点、按 K 个一组翻转链表、回文链表判断这一系列问题。它不是一道孤立的题而是一整套链表操作逻辑的缩影。无论你用的是 C、C、Java 还是 Python核心思路完全通用我今天以 C 为主但思路对任何语言都适用。1. 反转链表到底在考什么看一道题先别急着敲代码。你先把题目原文吃透给你单链表的头节点 head请你反转链表并返回反转后的链表。就这一句话。LeetCode 给了两个示例一个 1-2-3-4-5 反转为 5-4-3-2-1另一个是空链表反转后还是空链表。题干简单到不能再简单但这道题的通过率并不高为什么因为链表操作的本质是指针的重新编排你一旦在代码里丢失了某个节点的引用整个链表就断成两截了。1.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) {} };定义非常简单一个数据域 val一个指针域 next。val 存当前节点的值next 指向下一个节点的内存地址。最后一个节点的 next 指向空指针 nullptr。这就是链表和数组最大的区别——数组在内存里是连续的一块区域而链表的节点散落在内存各处靠指针串成一条链。这个结构决定了链表的一个核心特性你不能像数组那样通过下标随机访问某个节点你只能从 head 开始一个节点一个节点地 next 过去。另一方面链表的插入和删除操作只要修改指针就行不需要像数组那样搬移大量元素。反转链表这个操作本质上就是对每个节点的 next 指针做转向让原本指向前方的指针统统指向后方。1.2 直白思路为什么不可行很多人第一次做这道题的时候会有一个特别朴素的想法我能不能创建一个新链表然后从后往前遍历原链表一个一个头插到新链表里这个思路方向是对的但它有一个致命的缺陷——单向链表没办法从后往前遍历。因为你只有一个 next 指针走到最后一个节点之后你知道它的前一个是哪个吗不知道。你只能重新从 head 开始找倒数第二个节点。这样一来时间复杂度直接飙升到 O(n²)题目的数据量稍微大一点就超时了。要是题目改成给你一个双向链表那这个思路完全可以成立因为双向链表有 prev 指针可以从后往前走。但单向链表不行。所以我们必须换一个角度不从遍历顺序入手而从指针转向入手。反转链表不是把节点重新排列而是把每个节点的 next 指针指向它的前驱节点。这个视角一换解法就出来了。2. 迭代法三指针教你做人迭代法是反转链表最经典、最直观的解法。思路一句话用一个指针 pre 指向当前节点的前一个节点用一个指针 cur 指向当前节点每次循环时把 cur 的 next 指向 pre然后三个指针整体向后移动一位。2.1 初始化状态与循环不变量来先定义三个指针ListNode* prev nullptr; // 前驱节点初始为 nullptr ListNode* curr head; // 当前节点初始为头节点这里有几个初学者最容易懵的点。第一个问题是为什么 prev 要从 nullptr 开始因为反转之后原来的头节点会变成新链表的尾节点而尾节点的 next 必须指向 nullptr。所以第一步操作必然是让 head 的 next 指向 nullptr这个指向空的动作本质上就是把 head 的前驱节点当作 nullptr 来处理。第二个问题是为什么不需要额外的 next 指针其实需要但不是在初始化阶段定义而是在循环体内赋值。因为一旦你执行了curr-next prevcurr 原来的下一个节点就找不到了你必须在修改之前先把后继节点存下来。第三个问题是循环不变量。这个概念很多刷题的人不重视但它非常关键。在这个循环里我们维护的核心不变式是prev始终指向已经反转完成的链表的头节点curr始终指向尚未反转的链表的头节点。循环每执行一次效果就是把当前节点摘下并接到已反转链表的头部然后两个指针同步前进。搞清楚这个不变式你写循环体的时候就不容易乱。2.2 循环体执行过程与代码实现循环体的执行过程我用文字模拟一遍。初始状态原链表1 - 2 - 3 - 4 - nullptrprev nullptrcurr 节点1第一步用一个临时变量ListNode* next curr-next保存节点2。为什么必须保存因为马上执行curr-next prev之后节点1的 next 就从指向节点2变成指向 nullptr节点2就丢了。这个操作有点像断尾求生但在断之前你先把尾巴攥手里。第二步curr-next prev。节点1的 next 现在指向 nullptr。第三步prev curr。prev 从 nullptr 变成节点1。第四步curr next。curr 从节点1变成节点2。一轮循环结束。你可以自己画一下此时 prev 指向节点1反转后的新链表头curr 指向节点2剩余链表的头。第二轮循环开始节点2的 next 指向节点1prev 变成节点2curr 变成节点3。依此类推当 curr 遍历到原链表的末尾nullptr时循环终止此时 prev 刚好指向原链表的最后一个节点也就是反转后的新头节点。完整代码如下class Solution { public: ListNode* reverseList(ListNode* head) { ListNode* prev nullptr; ListNode* curr head; while (curr ! nullptr) { ListNode* next curr-next; // 先保存后继 curr-next prev; // 指针转向 prev curr; // 前驱前进 curr next; // 当前节点前进 } return prev; // 新的头节点 } };我见过很多人把这三步的顺序写错。最常见的错误是先执行prev curr再修改 next这样会导致修改 next 的时候 prev 已经变成了当前节点本身完全乱套。记住一个口决先记账再翻脸最后往前走。先记下后继节点再反转指针最后移动 prev 和 curr。顺序错了代码必崩。2.3 边界条件与细节验证迭代法写完之后一定要自己跑一遍边界用例。我整理了几个必测的场景场景输入预期输出验证重点空链表nullptrnullptr循环不进直接返回 prevnullptr单节点1 - nullptr1 - nullptr循环执行一次1 的 next 指向 nullptr双节点1 - 2 - nullptr2 - 1 - nullptr验证连续两次指针转向多个节点1-2-3-4-55-4-3-2-1完整流程验证循环终止条件空链表的情况代码直接返回 prev此时 prev 是 nullptr完美通过。单节点的情况循环体只执行一次next 是 nullptrcurr-next 指向 nullptrprev 变成节点1curr 变成 nullptr然后循环终止返回节点1。完全没有问题。双节点的情况稍微复杂一点但只要你把每一步都画出来基本也不会出错。这里我强调一个问题很多人在循环体里漏掉了保存 next 的那一行导致修改 curr-next 之后原本的后继节点丢失链表从中间断开。这个 bug 在用例规模小的时候不容易发现因为节点丢失后程序不一定立刻崩溃只是输出结果变短了。调试这类问题的一个好方法是在每一步循环之后打印 prev 和 curr 指向节点的值观察它们是否按照预期前进。迭代法的时间复杂度是 O(n)因为我们需要遍历链表的所有节点。空间复杂度是 O(1)因为只用了有限的几个指针没有使用额外的存储空间。这也是面试官偏爱这道题的原因之一——它在常数空间内完成了链表的原地反转。3. 递归法让计算机替你做重复劳动迭代法讲完了但反转链表还有另一种思路就是递归。递归的代码看上去比迭代法更短但理解起来要难一些尤其是递推关系这一步不知道卡了多少人。3.1 递归的核心思想递归法解决反转链表有一个非常优雅的思路。你先别去想整个链表怎么反转你想一个问题如果当前节点是 head而 head-next 后面那一整段链表已经反转好了那么你只需要做两件事就能让整条链表反转让 head-next-next head也就是让原链表的第二个节点反过来指向第一个节点。让 head-next nullptr也就是让第一个节点成为新链表的尾节点。就这两步。剩下的问题变成了如何让 head-next 后面那一整段链表反转答案是递归地调用同样的函数。这就是递归法最核心的递推公式。我画个图说明。假设原链表是 1 - 2 - 3 - 4 - nullptr我调用 reverseList(1) 的时候先递归调用 reverseList(2)递归调用 reverseList(3)递归调用 reverseList(4)。当调用 reverseList(4) 时发现节点4的 next 是 nullptr这是递归的终止条件直接返回节点4。然后一层一层向上回溯。回到节点3这一层时节点3-next 是节点4而节点4后面已经是反转好的 nullptr。此时节点4是这段链表反转后的新头节点也就是递归调用的返回值。现在对节点3执行两步操作节点3-next-next 节点3也就是把节点4的 next 从 nullptr 改为指向节点3节点3-next nullptr让节点3成为新的尾节点。此时以节点4为头、节点3为尾的这段链表就反转完成了。类推到节点2、节点1整个链表就反转完成了。3.2 递归函数的代码实现用 C 实现的递归代码如下class Solution { public: ListNode* reverseList(ListNode* head) { if (head nullptr || head-next nullptr) { return head; } ListNode* newHead reverseList(head-next); head-next-next head; head-next nullptr; return newHead; } };注意这里终止条件的写法。为什么不直接写if (head nullptr)因为当链表只有一个节点的时候它已经是一个反转后的链表你不需要再做任何操作。如果只判断 head nullptr那么单节点链表会继续执行head-next-next head这时候head-next本来就是 nullptr访问nullptr-next直接段错误。写递归的时候你始终要抓住一个信念递归调用一定能够完成任务。你不需要知道递归内部每一步是怎么执行的你只需要信任它能返回一个已经反转好的子链表的头节点。这个信念看似玄学其实是递归的核心逻辑。我曾经带过几个新人他们学不会递归就是因为总是试图在脑子里一层一层地展开所有调用展开到第三层就乱了。正确的学习方式是先用小例子验证递推公式是对的然后放心地让计算机替你去展开。3.3 递归的几点心得与易错点递归法写起来非常简洁但有几个细节我必须单独拎出来讲都是出血总结出来的经验。第一个细节是返回值的问题。递归最深层的返回值是原链表最后一个节点在回溯过程中这个返回值会一直被拿来作为 newHead 传递出去。所以不管递归嵌套到多深最终返回给你的新链表头节点就是原链表的尾节点。这个一定要想清楚否则你最后返回的可能是错误节点导致链表少一半。第二个细节是 head-next-next head 这一步的赋值顺序。我们必须先把 head-next-next 赋值为 head再把 head-next 赋值为 nullptr。如果顺序反了先执行 head-next nullptr那么 head-next 就变成了 nullptr再执行 head-next-next 就是在访问空指针必然崩溃。本质上这两步操作中第一步是在接上新指针第二步是在断掉旧指针。任何涉及指针修改的操作都要保证先接后断确保不会丢失对节点的引用。第三个细节是递归的空间复杂度。虽然递归的代码看起来只需要一个变量但每次递归调用都会在函数调用栈上压入一层栈帧直到终止条件触发。对于长度为 n 的链表递归深度也是 n空间复杂度就是 O(n)。这和迭代法的 O(1) 相比是一个劣势。当链表的长度达到上万甚至更多的时候递归法极有可能因为栈溢出而失败。所以这里给一个建议如果你在论文里或者项目代码里真正需要一个反转链表的功能建议优先使用迭代法如果你在面试中选择了递归法要主动向面试官说明递归的空间开销以及你了解如何转换为迭代实现。这样反而能加分。4. 迭代与递归的对比以及边界条件的完整梳理两种解法都讲完了现在把两者放在一起做一次系统的对比。很多人面试的时候把这题默写出来就完事了但面试官往往会追问一句你这两种解法优缺点是什么 你要是答不好代码写得再漂亮也白搭。4.1 两种解法的全维度对比对比维度迭代法递归法时间复杂度O(n)O(n)空间复杂度O(1)O(n)递归调用栈代码长度中等需要临时变量 next较短无显式临时变量理解难度直观适合新手抽象需要递归思维工程落地推荐无额外开销谨慎大链表可能栈溢出LeetCode 实测稳稳但极端数据可能爆栈迭代法的空间优势非常明显因为链表本身是线性数据结构用循环遍历天然合适。递归法的代码虽然优美但本质上是利用了函数调用栈来存储每个节点的状态这是一种隐性的空间开销。如果你的链表长度是几十万甚至上百万递归法很可能直接把系统栈打爆。这也是为什么在很多生产环境的代码规范里都对递归深度有严格的限制。4.2 常见边界条件快速速查我用力整理了一份反转链表边界条件速查表每次写完代码之后对照这张表逐项验证可以避免大量低级错误边界场景迭代法验证要点递归法验证要点空链表head nullptr返回 nullptr终止条件命中返回 nullptr单节点链表prev 初始为 nullptr循环一次后返回节点本身终止条件命中返回该节点双节点链表关注循环两次后 prev 与 curr 的位置递归深度 2回溯一次完成反转长链表性能仅遍历一次无额外分配注意栈深度可能导致栈溢出链表中含重复值不涉及值比较正常反转不涉及值比较正常反转每次考试、面试、写代码之前把这些场景在脑子里过一遍基本上就能杜绝空指针和时间超限的问题。尤其是单节点很多人只判断了 head nullptr忘了判断 head-next nullptr在递归法中直接段错误迭代法虽然不会崩但返回值会变成 nullptr新链表凭空消失。4.3 一个经常被忽略的陷阱引用传递刷题的时候大家一般都传的是指针用的是ListNode* head这时候不会出幺蛾子。但如果在项目代码里有人把函数签名设计成ListNode* head引用传递那你就要小心了。传引用意味着你可以直接修改 head 本身而不是修改 head 指向的内容。在反转链表的场景中如果你直接修改了 head 的指向那么函数外部原本保存的头节点变量就再也拿不到原链表的头了。如果函数签名确实传了引用那么正确的做法是在函数内部先用一个临时指针保存原始 head然后操作其他指针完成反转最后在返回之前再决定要不要把 head 更新为新头节点。这个细节非常隐蔽面试官出了名的喜欢在这一类签名上挖坑。你平时练习的时候建议两种签名都写一遍感受一下差异面试的时候就算遇到也不会慌。5. 面试场景下的完整答题链路这题在面试中出现的频率实在太高了几乎可以算作链表类题目的入场券。很多公司的第一轮算法考察就会出这道题因为它的难度适中能筛掉完全没有链表概念的人同时又有足够多的延展空间能考察候选人的深度。下面复盘一条我在实际面试中总结出的完整答题链路从拿到题目到最后收尾的每一个环节。5.1 从审题到动笔的标准流程第一步先重复确认题目约束。面试官说完反转链表你先反问几个问题链表是单向还是双向是原地反转还是可以创建新链表链表的节点数值有无特殊限制函数的返回值应该是新链表的头节点吗 这些提问看起来像是确认细节实际上是在向面试官展示你有边界意识。实际上 LeetCode 原题默认是单向链表、原地反转但面试现场口头描述可能不一样你多问一句不会出错。第二步先描述思路再写代码。不要拿到题目直接闷头写先把迭代法的思路用自然语言说出来我打算用三个指针prev 作为已反转部分的新头cur 作为当前要处理的节点用一个临时变量保存 cur 的后继然后每一轮把 cur 的 next 改为 prev最后返回 prev。 这一步非常关键因为它让面试官知道你脑子里的规划。很多候选人代码写得没错但讲不清楚思路最后反而评价不高。第三步在白板或编辑器里写代码注意代码风格的规范。变量名不要用 a、b、c 这种无明显含义的字母尽量用 prev、curr、next 这样的全称。面试官会通过你的命名习惯来判断你的工程素养。写完代码之后一定要主动在代码注释中标注循环不变量的含义体现出你不只是在背题而是真的理解了这道题的运行逻辑。第四步主动讲复杂度分析。复杂度不是面试官逐字逐句问的你就应该在讲完代码之后主动说这个解法的空间复杂度是 O(1)时间复杂度是 O(n)因为我们只遍历了整个链表一遍并且只用了常数个额外指针。 这句话能展示你对算法效率的敏感度。5.2 面试官的灵魂追问回答完标准解法之后面试官大概率会抛出下面的追问第一个追问是你还能想到别的解法吗 这时候你就把递归法讲一遍。讲的时候注意强调递归的终止条件head nullptr || head-next nullptr以及递推关系head-next-next head和head-next nullptr最后点明递归的空间复杂度是 O(n)。这样既展示了知识的广度又展示了深度。第二个追问是如果列表有环你的反转会怎么样 这个问题很刁钻。迭代法在有环链表中会无限循环因为 curr 永远不会变成 nullptr你需要在循环中增加一个访问标记来检测环。递归法会栈溢出因为递归无法到达终止条件。一个稳妥的答案是先说明标准的 LeetCode-206 默认是无环链表如果面试官强行要求处理有环场景我们还需要实现一个环检测例如快慢指针作为前置步骤。回答的框架是场景澄清 风险识别 兜底方案这也是团队协作里非常重要的一项软技能。第三个追问是你能原地反转链表的某一段吗 这是 LeetCode-92 题反转从 left 到 right 的 skr 节点区间。实现思路是基于基础反转做一个扩展先遍历到 left 的前一个节点然后对该区间内的节点做反转再把反转后的头尾节点与前后部分重新接上。核心还是利用迭代法但需要额外记录区间前驱和后继节点。如果你基础反转写得够熟这题的代码只是在一个循环外面加了一些连接操作难度并不高。5.3 进阶变种题目一览说到了变种题我干脆把基于反转链表这个核心操作衍生出的常见题目整理成一个清单方便你按图索骥地练习LeetCode-92反转链表 II。给定 left 和 right反转区间内的节点。核心技巧是定位区间后复用基础反转逻辑再把区间两端与外部链表接好。LeetCode-25K 个一组翻转链表。把链表按长度为 K 的子链分组组内反转组间串联。是反转链表的进阶应用面试高频中的高频难度明显上了一个台阶。LeetCode-234回文链表。判断一个链表是否为回文。经典解法是先用快慢指针找中点再把后半段链表反转然后逐节点比对。反转在这里是辅助操作。LeetCode-143重排链表。要求将链表原地调整为 L0 - Ln - L1 - Ln-1 - ...。思路是找中点、反转后半段、合并两条链表每一步都用到了链表基本功。LeetCode-24两两交换链表中的节点。虽然题目不叫反转但交换两节点在实现上需要大量指针操作和反转链表的思想一脉相承。如果你能把基础反转讲透、写对、答出复杂度分析那么上面的变种题你已经有六七成的底子了。剩下的无非是在基础模型上增加边界状态管理的技巧。6. 实操验证与测试用例的设计思路光说不练假把式。我建议你拿到代码之后不要马上在 LeetCode 上提交而是先本地搭建一个测试环境自己构造几个测试用例逐步验证。这样不但能确保代码正确更重要的是帮你建立工程级的调试思路。下面我把完整测试链路写出来你可以直接复制用。6.1 构造链表与打印工具函数在 C 中测试链表题需要两个辅助函数一个根据数组创建链表一个打印链表。代码很短但特别有用#include iostream #include vector using namespace std; // 根据数组创建链表返回头节点 ListNode* createList(const vectorint arr) { if (arr.empty()) return nullptr; ListNode* head new ListNode(arr[0]); ListNode* cur head; for (int i 1; i arr.size(); i) { cur-next new ListNode(arr[i]); cur cur-next; } return head; } // 打印链表所有节点的值 void printList(ListNode* head) { while (head ! nullptr) { cout head-val; if (head-next ! nullptr) cout - ; head head-next; } cout - nullptr endl; }打印函数有一个好处当你看到输出结果变成5 - 4 - 3 - 2 - 1 - nullptr一切尽在掌握。这个打印函数在调试所有链表题时都通用建议直接加入你的算法工具箱。写测试用例时别只测一个样例。多测几个程序跑不坏你。6.2 多组用例的实测输出对照假设我们构造如下几个测试输入并依次调用迭代解法int main() { vectorvectorint tests { {}, {1}, {1, 2}, {1, 2, 3, 4, 5} }; for (auto arr : tests) { ListNode* head createList(arr); cout 原始链表: ; printList(head); ListNode* reversed reverseList(head); cout 反转链表: ; printList(reversed); cout endl; } return 0; }理想输出如下原始链表: nullptr 反转链表: nullptr 原始链表: 1 - nullptr 反转链表: 1 - nullptr 原始链表: 1 - 2 - nullptr 反转链表: 2 - 1 - nullptr 原始链表: 1 - 2 - 3 - 4 - 5 - nullptr 反转链表: 5 - 4 - 3 - 2 - 1 - nullptr在实际调试的时候很多人会忽视最后一个用例直接拿示例的数据去提交。结果在小数据量下没什么问题但一旦数据量变大就暴露出循环终止条件写错的问题如果终止条件写成了while (curr-next ! nullptr)那么当链表长度为偶数时就会把最后一个节点丢掉。用多组用例覆盖不同长度的链表能有效规避这一类隐蔽的差一错误。6.3 常见的几个本地调试坑本地测试还有一个经常踩的坑反转过程中修改了原链表导致你在测试完迭代法之后试图用 createList 的结果继续测试递归法时链表已经不是原始状态了。遇到这种情况最简单的处理方式是为每组测试重新创建一次链表对象而不是复用已反转的 head。你在工程开发中修 bug 也要养成这个习惯——不要在同一片数据上反复模拟不可逆操作除非你真的了解每一步的状态变化。另外一个本地调试的坑是内存管理。C 里new出来的节点不会被自动回收你写完测试代码之后如果不手动 delete在 LeetCode 上没问题但本地长期跑会内存泄漏。虽然刷题阶段大家一般不太在意这个但我要提醒你很多企业的手撕代码环节对内存泄漏是有要求的面试官可能会打开 sanitizer 检查你的代码。你在提交代码前可以快速扫一眼有没有无主的 new这也是锻炼工程素养的机会。7. 从刷题到落地为什么这题值得反复咀嚼刷 LeetCode 刷到 130 天很多人会进入一种麻木状态每天做一题提交通过打卡划掉。但如果你只是这么机械地重复那刷 1000 题也提升不了多少。反转链表这道题最值得你做的事情不是把它背下来而是把它当一个方法论的试验田反复咀嚼。我自己再回头看这题的时候会从三个层次去复盘。第一层是代码层我能不能不看答案在五分钟内写出无 bug 的迭代和递归解法。第二层是思维层如果我手里拿的不是链表而是数组、二叉树我要反转一个线性结构能不能抽象出类似的双指针逐步扭转的思维模型。第三层是工程层在真实项目里如果数据规模很大对性能要求很高我应该选择迭代法如果代码可读性更重要递归法是不是更好的选择。这道题之外我还特别推荐你仔细研究一下反转链表 II和K 个一组翻转链表。这两道题堪称反转链表的全家桶。你会发现它们的核心代码框架和基础反转几乎一模一样差别只在于边界条件的处理。真正吃透一道题不是背下一段代码而是把它的变种也吃透。刷题的目的从来不是数量而是你能否在变化中识别出那道不变的底牌。反转链表是链表操作的核心中的核心。把它真正弄懂你的链表基础就算打牢了。遇到不懂的细节比如递归回溯的赋值顺序、迭代循环的终止条件都建议自己多画几次图。画图是理解链表操作最有效的方法没有之一。你花在画图上的时间最终会以数倍的速度回馈给后续每一道链表题。我在刷题早期每道链表题都画图到现在遇到再复杂的指针操作脑子里都能自动播放链表的动态变化过程这就是耐心画图带来的红利。