反转链表这道题在算法题单里的存在感不需要我多说。任何一个走过面试流程的开发者十有八九都被它问过。我当年准备跳槽那会儿把链表题刷了一圈最后发现一个有意思的现象很多看似复杂的链表题解到深处都是“反转”这个基础动作的影子。“206 反转链表”作为 LeetCode 上编号最小的链表题之一看似只有短短几行代码但它真正考察的是你对“指针”、“引用”、“递归”这些底层概念的肌肉记忆。很多人觉得这题简单背个迭代写法就过了。但真的在面试现场面试官往往不会满足于你背出代码。他会追问递归的返回值为什么是 newHead迭代里 pre 指针为什么初始化为 null如果链表有环你的代码会不会死循环这些问题的答案恰恰是区分“背题”和“理解”的分水岭。这篇文章我想从原理、迭代、递归、变种到调试把这题掰开揉碎讲清楚。目标很直接你看完这篇不但能写出代码还能把每一步操作的“为什么”说出来遇到任何追问都能接得住。1. 反转链表的本质先想清楚它到底考什么1.1 链表题目前的核心素养指针思维很多同学做链表题习惯性把它当成数组来想。数组反转怎么做直接交换 arr[i] 和 arr[n-1-i] 就行因为有下标。链表没有下标它只有一个一个的节点每个节点只知道自己和下一个节点是谁。这意味着你没办法随机访问任何一个节点也不可能“原地交换”两个不相邻节点的值——你连它们的地址都够不到。所以链表操作的本质是改指针。反转链表就是要把每个节点的 next 指向前一个节点让整个链的方向掉个头。这个过程听起来简单但一旦你开始动手改问题就来了当你把 A 节点的 next 从 B 改成 prevB 节点就没人指向它了如果你之前没有保存 B 的地址你就永远失去它了。这就是链表题里最常见的翻车点——断链。1.2 反转操作的工程意义比你想象中更多我经常听到有同学问“这题工作中用得到吗”说实话直接用得到的机会不多但它的思想无处不在。举几个场景回文链表的判断需要先找到中点然后反转后半段链表再逐位比较。双向链表的反序遍历有些场景为了省空间不用栈直接把链表反向后遍历再转回来。数据库或底层框架里的 LRU 缓存结构内部也是双向链表的变体一旦需要“逆序驱逐”就涉及方向调整的思路。更别提在学习二叉树反转、图遍历等更复杂的数据结构时递归和指针传递的思想都跟这道题同根同源。说白了“反转链表”就是指针操作的基础课后面所有链表高级操作都是在这节课上盖楼。地基不牢后面刷题时你遇到“K 个一组反转”、“奇偶链表排序”都会带着理解上的模糊。2. 迭代法实战三指针滑动5行代码解决战斗2.1 三指针的初始化pre 为什么必须是空迭代法的核心思路是让链表上的每个节点把它的 next 从指向下一个节点改成指向上一个节点。要实现这个目标你必须在遍历时同时知道三个信息当前节点是谁、它的上一个节点是谁、它的下一个节点是谁。于是就有了三个指针pre当前节点的前驱初始时指向nullptrcur当前正在处理的节点初始时指向头节点headnext当前节点的后继用于保存断链之前的位置第一次写这个代码的人最容易犯的错是把pre初始化为head。这看起来好像没问题“第一个节点前面没有节点那它自己不就是前驱吗”不对你仔细想反转完成后原来的头节点会变成新链表的尾节点而尾节点的 next 指向的是空不是它自己。如果你把 pre 初始化为 head反转后尾节点会指回自己链表瞬间变成一个环各种遍历都会死循环。2.2 循环体内的三步走保存、反转、推进核心循环非常简单标准写法如下ListNode* reverseList(ListNode* head) { ListNode* pre nullptr; ListNode* cur head; while (cur ! nullptr) { ListNode* next cur-next; // 第1步保存后继 cur-next pre; // 第2步反转指向 pre cur; // 第3步pre 前进 cur next; // 第4步cur 前进 } return pre; }四行循环体步骤顺序极其关键。第一步为什么必须先保存 next因为第二步一旦执行cur-next 就会被覆盖成 pre原来的后继节点就找不到了。如果不保存循环继续时 cur 根本没办法向后走整个遍历就断了。第二步“反转指向”是整个算法的灵魂。执行前cur 的 next 还指向下一个节点执行后cur 的 next 指向前一个节点这一步完成了当前节点的“反转”。第三、四步是“双向前进”pre 移动到 cur 的位置cur 移动到之前保存好的 next 位置。这里要注意为什么不是先移动 cur 再移动 pre你试一下就知道如果把第3步和第4步调换pre 指针指向的就不是当前处理完的节点而是下一个节点整个顺序就乱了。我用一个生活化的例子帮你理解这就像在档案馆里整理一排档案盒你面前一摞档案你要把它们一个一个搬到另一边的空架子上。你每次从旧架子上拿一个档案先用手挡住下一个档案的位置保存 next再把当前档案放到新架子上反转指向然后旧架子那边的新位置成为你已经整理好的位置pre 前进你再去拿刚才挡住的那个档案cur 前进。整个过程循环往复等旧架子的档案全部拿完新架子上就是一摞完全倒序的档案。2.3 边界情况要单独确认空链表和单节点写完代码之后有经验的工程师都会养成一个习惯用边界条件来验证逻辑。这个习惯在面试中极其加分因为很多人写完就喊“过了”但面试官真正关心的是你思考问题的严谨性。空链表head 为 nullptr循环根本进不去直接返回 pre也就是 nullptr。这符合“空链表反转后还是空链表”的预期。单节点链表head-next 为 nullptr。进入循环第一步保存 next为 nullptr第二步 cur-next 指向 prenullptr第三步 pre 变成 head第四步 cur 变成 nullptr。循环退出返回 pre也就是原来的单个节点。反转后还是它自己正确。两个节点head-next 是第二个节点。第一步保存 second第二步 head-next 指向 nullptr第三步 pre 变成 head第四步 cur 变成 second。第二轮保存 nextnullptr第二步 second-next 指向 head第三步 pre 变成 second第四步 cur 变成 nullptr。返回 pre 即 second。链表方向完全反转。边界条件没问题说明代码逻辑是自洽的。面试时把这个过程说出来效果远比你直接写代码要好得多因为面试官能看到你是“想清楚了再写的”。3. 递归法详解把“从后往前翻”想明白3.1 递推公式先反转剩下的再处理当前节点迭代法的思路是“从前到后逐步反转”递归法的思路则是“从后到前逐步反转”。它的核心思想是递归假设假设我写一个函数 reverseList(head)它能反转以 head 为头节点的整个链表并返回新的头节点。那么对于当前链表的子问题我可以先调用 reverseList(head-next)把 head 之后的剩余部分全部反转然后再处理 head 本身与新链表尾部的连接关系。这句话第一次看很绕我换个方式讲。你的链表是1 - 2 - 3 - 4 - nullptr现在你想反转它。递归会这么想问题“我先把2 - 3 - 4 - nullptr这段反转了得到4 - 3 - 2 - nullptr新的头是 4。”“现在原链表的头 1 还在最前面它后面原来跟着的是 2。可是 2 已经跑到反转后的链表的尾部去了。”“所以我只要让 2 指向 1让 1 指向 nullptr就完成了整个链表的反转。”这句话是真的关键。你要记住head-next在反转前指的是原来的第二个节点反转后这个节点变成了反转链表的尾部节点。因此head-next-next head就是在原来第二个节点后面挂上当前节点。最后head-next nullptr是因为当前节点现在变成了尾节点尾节点的 next 必须为空。3.2 递归代码的执行轨迹与指针变化看代码是最直接的方式。以简洁的 C 为例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; }我逐层拆解执行过程。假设链表是1 - 2 - 3 - nullptrreverseList(1) 进来head 是 1。head-next 不是空递归调用 reverseList(2)。reverseList(2) 进来head 是 2。head-next 不是空递归调用 reverseList(3)。reverseList(3) 进来head 是 3。head-next 是空直接返回 3。回到 reverseList(2)拿到 newHead 3。执行 head-next-next head也就是 3 的 next 指向 2。执行 head-next nullptr让 2 指向空。返回 newHead 3。此时链表内部结构变为1 - 2 - 32 指向空。回到 reverseList(1)拿到 newHead 3。执行 head-next-next head也就是当前 head 是 1head-next 是 2让 2 的 next 指向 1。执行 head-next nullptr让 1 指向空。返回 newHead 3。到这一步为止完整链表已经变为3 - 2 - 1 - nullptr。注意第5步中原来 2 的 next 是 nullptr但这时 head-next 是 22-next 已经是 3 反转过后的结果其实在第4步结束时2 的 next 被设置为了空。但是在第5步你要修改的是“head 的 next 的 next”。由于 head1head-next2所以修改的就是 2-next让它指向 1。这步操作把第4步设置的“2-next nullptr”给覆盖掉了。它原本是空的也没关系因为你就是要让它指向新的前驱。这里有一个初学者容易懵的地方为什么第4步执行了head-next nullptr之后第5步还能通过 head-next 找到 2因为 head 是局部变量每次递归调用都有自己的 head第5步里的 head 是第1层的节点1它从头到尾没有被修改所以它依然保存着对节点2的引用。递归层层的局部变量各管各的互不干扰。3.3 两种解法的复杂度对比与面试选择建议从时间和空间复杂度来看解法时间复杂度空间复杂度主要风险迭代法O(n)O(1)指针顺序写错导致断链递归法O(n)O(n)链表过长导致栈溢出面试时怎么选我的建议是能写迭代就优先写迭代。原因很多递归法虽然代码短但空间复杂度是 O(n)对于工程实现不够友好。在极端情况下比如链表有 10 万个节点递归的调用栈可能会直接爆掉这在线上环境是会出事故的。面试官如果问你“能不能优化空间复杂度”你就得从递归改成迭代不如一开始就用迭代法。但递归法也不是没有价值。很多更复杂的链表题比如“反转链表的前 N 个节点”、“K 个一组反转链表”递归思路能让你更快写出简洁的解法。所以我的学习建议是迭代法和递归法都要掌握但面试作答时优先展示迭代法然后主动提一句“递归法也能实现我需要解释一下吗”这就把选择权交给面试官显得你知识体系完整还知道做取舍。4. 从基础题到变种题局部反转与 K 个一组反转4.1 反转区间链表加一个哨兵节点能省一半事“206 反转链表”是反转整个链表但面试官经常会在你做完之后追加追问“如果只反转中间某一段呢比如链表的第 2 个节点到第 4 个节点你能实现吗”这就是 LeetCode 92“反转链表 II”的考点。反转区间[left, right]的基本思路并不复杂先把区间内的节点挨个“摘下来”用插入法重新串起来。但我见过太多人在边界处理上翻车。为什么因为区间可能从第 1 个节点开始这时候根本没有前驱节点你得特判。解决这类问题的常规武器是哨兵节点dummy node。ListNode* reverseBetween(ListNode* head, int left, int right) { ListNode* dummy new ListNode(0); dummy-next head; ListNode* pre dummy; // 1. 让 pre 指向区间前一个节点 for (int i 0; i left - 1; i) { pre pre-next; } ListNode* cur pre-next; // 2. 头插法反转区间 for (int i 0; i right - left; i) { ListNode* next cur-next; cur-next next-next; next-next pre-next; pre-next next; } return dummy-next; }这段代码里的头插法思路值得重点讲。cur 始终指向区间内“当前第一个节点”每次循环把 cur 后面的那个节点摘出来插入到 pre 的后面。一次插入完成一次“把后节点搬到前面来”反复执行 right-left 次区间内的节点顺序就完全反转了。这个解法的好处dummy 节点让 left1 的时候不用特判pre 可以统一从 dummy 开始走边界情况自然而然被覆盖了。面试时你可以提一句“用一个虚拟头节点规避掉区间从头开始的边界问题。”这句话很加分。4.2 K 个一组翻转链表分组处理的通用套路再狠一点面试官会问“每 K 个节点一组进行翻转不足 K 个的保持原样能不能做”这就是 LeetCode 25“K 个一组翻转链表”。我刷这道题时最大的感受它把“反转整条链表”这个基础操作从一次性的动作变成了循环里的一个小组件。你需要做三件事数数检查从当前指针出发后面有没有 K 个节点。如果不足 K 个直接返回结果。分组反转对这 K 个节点调用一次局部反转。接链把反转后的这组节点和链表前后正确连接起来。这里面最不容易想清楚的是“局部反转”的接口设计。你不能直接调用反转整个链表的递归函数因为那会把整条链都反转了。我的做法是写一个辅助函数专门反转一小段链表并返回新头新尾ListNode* reverseKGroup(ListNode* head, int k) { ListNode* dummy new ListNode(0); dummy-next head; ListNode* pre dummy; while (pre ! nullptr) { ListNode* cur pre-next; // 检查是否够 k 个 int count 0; while (cur ! nullptr count k) { cur cur-next; count; } if (count k) break; // 反转当前组 ListNode* start pre-next; ListNode* nextGroup cur; // cur 已经是下一组的头 ListNode* prev nullptr; ListNode* node start; while (node ! nextGroup) { ListNode* temp node-next; node-next prev; prev node; node temp; } // 接回原链 pre-next prev; start-next nextGroup; pre start; } return dummy-next; }这个实现里的细节非常多。比如while (node ! nextGroup)判断的是“反转停止的边界”而不是“节点是否为 nullptr”。这是因为反转 K 个节点时我们需要把这 K 个节点处理完但不能动下一组的节点。如果你还是用 nullptr 作为终止条件就会把下一组也卷进来。另一个细节是反转完之后的链表拼接顺序pre-next 指向新头prevstart 指向下一组的头nextGroup然后把 pre 移到 start 的位置继续下一轮的判断。整个过程像流水线一样分组处理逐步推进。4.3 变种题里最容易踩的坑这些变种题里我总结出几个高频翻车点逐个说一下第一个坑是“没有保存剩余部分的节点引用”。在反转一组 K 个节点时如果你没有在循环前先把下一组的头结点地址保存下来反转结束后你就不知道怎么把链拼回去了。解决的方法是在开始反转前先让 cur 指针走 K 步这样 cur 就是下一组的头把它妥善保存。第二个坑是“数数和反转的边界不一致”。有的同学在反转时用node ! nullptr作为终止条件但数数时泰勒只做了 K 步这就会导致反转了 K1 甚至更多个节点。一定要让反转的终止条件和数数的结果严格对应我上面的代码中终止条件是node ! nextGroupnextGroup 是数数结束后 cur 停留的位置两者天然一致。第三个坑是“更新 pre 的顺序错误”。反转完一组后pre 应该移动到这一组的尾部。但在反转后的链表里这一组的头部是原来的 start尾部是原来的最后一个节点。注意代码里我最后执行的是pre start不是pre pre-next。因为执行完反转后pre-next已经指向了新的头节点如果你直接取pre-next就会跳到新头部而不是这一组的尾部。用 start 反而最稳妥因为 start 在反转前是这一段的头反转后它变成尾节点正是下一轮 pre 应该待的位置。这些细节你只看一遍代码可能记不住。我的建议是把这道 K 个一组反转的题拿出来专门在纸上慢慢推演两三遍每走一步都想想“这个节点的 next 现在是谁”“如果我现在做某个操作会丢失哪些引用”推过几遍之后你会形成一种直觉以后再遇到链表题心里就有底了。5. 踩坑实录与快速自测方案5.1 三次典型翻车案例复盘刷这道题时我自己踩过的坑不算少这里挑几个有代表性的分享一下希望你别再趟一遍。案例A忘了保存 next直接断链最早写迭代法时我把代码写成了这样while (cur ! nullptr) { cur-next pre; // 先反转 pre cur; cur cur-next; // 取 cur-next结果拿到的是 pre }看上去每一步都在走但执行第二步时 cur-next 已经被改成 pre 了所以第三步里 cur 取到的“next”其实是前一个节点导致 cur 不但没往前走反而回去了。如果是单链表第二步后 cur-next 指向前驱那 cur 再取 next 就回到了 pre形成原地打转链表永远遍历不完。这种情况面试时特别尴尬因为代码明明“看起来”是对的但跑起来就出事。案例B忘记中断尾节点的 next这个坑主要出现在递归法里。有的同学在递归返回时只写了head-next-next head却忘了写head-next nullptr。如果是非空链表最后的结果是原链表的头节点也就是新链表的尾节点仍然指向原链表的第二个节点两个节点互相指形成环。用这种链表做遍历程序会直接卡死。案例CK 个一组反转时把 pre 移动到错误的位置在变种题里反转完一组节点后我把pre pre-next当成固定动作结果导致 pre 指向了新链头而不是尾。下一轮反转时数数起点就错了整条链的结构也随之错乱。这个我当时调试了很久最终靠画图定位出来。5.2 快速自测的三步检查法刷链表题时我有一个固定的自测流程强烈建议你也养成习惯第一步看图对指针。找一个真实的小链表比如1 - 2 - 3 - 4用纸笔画一遍代码执行时每个指针的指向变化。画的时候最好把 pre、cur、next 三个指针标出来每走一步圈一下。这个动作看着慢实际上对建立直觉特别有效。第二步写边界测例。至少检查这三种情况空链表、只有一个节点、两个节点。对于变种题还要加上“反转区间在头部”“反转区间在尾部”“K 值等于链表长度”“K 值大于链表长度”等测例。第三步打印验证。写代码时可以临时加打印输出在每次循环中把 pre、cur、next 的值打出来。一旦结果和预期不符立刻就能看到是哪个节点的指针走位错了。确认正确后把打印删掉就行。5.3 面试现场从暴力思路到最优解的路子很多同学担心面试时一紧张就写不出来。我觉得这个问题可以通过“口头热身”来解决。面试官给你题目之后别急着动手敲代码先把思路梳理成一句话“我先用迭代法维护两个指针 pre 和 cur每次让 cur 指向 pre然后两个指针同步前进最后返回 pre。”这句话说出口的同时你的大脑已经完成了最底层的逻辑确认。接着再补充复杂度“时间复杂度 O(n)空间复杂度 O(1)。”这样面试官对你就有底了哪怕后面代码有小错误他也会知道你思路是对的而不是在瞎猜。如果面试官追问“能不能用递归实现”你可以先说明递归的空间代价“可以但空间复杂度会到 O(n)因为递归栈需要保存每一层的上下文。如果不要求空间最优我可以很快写出来。”然后果断把递归版本写给他看。这种“主动说明代价”的姿态比默默写完惊艳全场更接近真实的工程评审氛围。6. 反转链表不是刷题玩具真实场景里怎么用它6.1 回文链表判断反转一半就够了最直接的工程相关场景是判断回文链表。普通的数组判断回文很简单两个下标往中间靠就行。链表不行因为你不能从尾部往前遍历。常见的做法是先用快慢指针找到链表的中点然后把后半段反转再用两个指针同时从头部和中点开始逐个比较。bool isPalindrome(ListNode* head) { ListNode* slow head; ListNode* fast head; // 1. 快慢指针找中点 while (fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; } // 2. 反转后半段 ListNode* cur slow; ListNode* pre nullptr; while (cur ! nullptr) { ListNode* next cur-next; cur-next pre; pre cur; cur next; } // 3. 比较前半段和反转后的后半段 ListNode* left head; ListNode* right pre; while (right ! nullptr) { if (left-val ! right-val) return false; left left-next; right right-next; } return true; }这道题你要是不会反转链表就只能用栈来辅助空间复杂度 O(n)。会了反转空间复杂度立马降到 O(1)。这就是基础能力的直接换算。6.2 逆序输出与链式存储的思路复用还有一种实际场景是逆序输出。比如日志系统里你有一条链表形式的操作记录需要从最新到最旧展示。如果直接用递归输出同样有栈溢出的隐患如果直接反转链表就要考虑会不会影响其他模块对这个链表的引用。正确做法是复制出一条新链再反转或者使用栈辅助。这些方案的选择本质上都是在权衡时间、空间和副作用而这种权衡能力恰恰是刷链表题学到的。6.3 反向思维对工程设计的启发我做后端开发这么久发现“反转”这个操作在系统设计里也经常出现。举一个很简单的例子有些系统里为了照顾写入性能最新的数据放在链表头部但读取的时候需要按时间从旧到新展示。这时候你不一定要在存储层做反转可以在读取层用迭代法同样的思路做一遍遍历处理。它不会真的拷贝一份内存只是把遍历顺序换了一下。再比如做双向链表相关优化时你会频繁用到“改指针顺序”的思维。只要你写过一遍反转链表就能很自然地理解“断链之前先保存”这种意识在操作数据库字段、多线程并发环境下的引用替换时同样适用。先保存旧引用再修改新引用最后释放旧引用这个模式在工程里简直是万能模板。所以我觉得反转链表这道题虽然小但它训练的是你在操作复杂引用结构时的“手稳”。它逼你养成画图、推演、检查边界的行为习惯这些习惯会迁移到你设计和调试任何复杂系统的工作中。回顾我自己刷这道题的经历前后加起来大概写了不下十遍每写一遍都有新的体会。最开始是在白纸上画指针后来是纯手写代码再后来是给面试官讲思路。在这过程中最让我受益的不是最终背下来的那几行代码而是每一遍推演中对“为什么 pre 初始化是空” “为什么先保存 next”这些细节的确认。所以我的建议很朴素哪怕你已经能把代码流畅写出来也请多花一点时间把递归和迭代两种方式都推演一遍把变种题的边界条件亲手测一遍。这样刷一道题的效果可能比囫囵吞枣刷十道题都好。将来你遇到任何复杂的链表问题都会感谢现在认认真真推演过的这半小时。