K个一组翻转链表：迭代与递归两种解法详解

做力扣hot100刷到“K个一组翻转链表”这道题时我其实卡了好一阵。它排在hot100很靠前的位置不少朋友说这题“看着答案能懂自己写就废”我太理解这种感受了。题本身不涉及什么高深算法但链表指针一多绕来绕去就特别容易晕。这篇就把我自己的完整思路、两种写法、以及踩过的坑一次性说清楚希望能帮你把这题彻底拿下。这道题本质上考的是两块基本功一是链表反转的熟练度二是“按组切分再拼接”的边界处理。适合正在集中刷链表专题的人也适合准备面试前突击手写代码的同学。看完这篇你不仅能AC这道题以后遇到类似的“分段处理链表”问题思路也会清晰很多。1. 题目理解与核心思路拆解1.1 题面到底在说什么先别急着看代码把题读透。题目给你一个单链表要求每k个节点为一组在组内做反转然后组与组之间保持原有顺序。最后如果剩余节点不足k个就保持原样不动。举个例子链表是 1-2-3-4-5k2。两两一组1、2是一组反转变2-13、4是一组反转变4-35不够一组保持5。最终结果是 2-1-4-3-5。如果k3那就是 3-2-1-4-5因为4、5不足3个节点不翻转。这里有几个关键理解题目要求“实际进行节点交换”不能只改节点里的值。有些人会投机取巧把链表转成数组反转数组再填回去。这样在力扣上也能过但面试官一眼就能看穿而且这完全违背了这道题考察链表操作的初衷。“剩余不足k个保持原样”这个条件决定了你必须在翻转前先判断当前这一组是否凑够了k个节点。k等于1或者链表为空时结果就是原链表这种边界情况虽然简单但很容易在写通用代码时被忽略。1.2 为什么说这题的核心是“分段”我第一次做这题时脑子里的想法是从头开始每数k个就翻一次一直翻到结尾。听起来很简单但一上手就发现几个问题翻转一组之后怎么找到下一组的起点上一组的尾节点怎么和下一组的头节点接上如果最后不够一组怎么知道该停在哪这些问题都指向同一个能力对链表片段进行精准的区间操作。你不能像数组那样直接下标访问只能靠指针一个一个走。所以这道题的通用解法是先定位一组区间再把区间内的链表反转最后把区间重新接回主链表。整体框架就是“定位 - 断开 - 反转 - 接回 - 移动”的循环。用生活里的例子类比一下你有一串珍珠项链要求每隔k颗就把这一段倒过来串。手工操作时你会先把这一段从整条项链上解下来倒序串好再把它装回去。链表操作其实也是这个流程。解下来是为了反转时不受其他节点干扰装回去是为了保持整条链的完整性。1.3 两种主流方案迭代与递归针对这个框架业界最常见的两种实现思路迭代法维护几个指针在while循环里不断切分、反转、拼接。优点是空间复杂度O(1)缺点是变量多容易绕晕。递归法每一组翻转的逻辑通过递归函数完成代码更简洁思路更符合“拆子问题”的直觉。代价是递归栈会占用额外空间空间复杂度O(n/k)。两种方法我都建议掌握。迭代是面试手撕的稳妥选择递归则能帮你在分析问题时更快找到思路。后面我会把两种写法的细节都展开并且对比它们的取舍。2. 核心细节解析迭代解法完整剖析2.1 为什么要引入虚拟头节点链表题里虚拟头节点dummy node几乎是处理“头节点可能被修改”问题的标配。这题的最终结果头节点大概率会变——比如 1-2-3-4-5 且 k2 时新头是2。如果你不引入 dummy就得单独处理“新头是谁”这个问题非常繁琐。dummy 的思路很简单在真正链表的头部之前再造一个哨兵节点。它的 next 指向 head。不管链表怎么翻转最终返回 dummy.next 就是新链表的头。这样一来你就不用为头节点的变化单独写逻辑了。我用迭代法写的时候需要维护两个关键的组间指针pre当前待翻转区间的前一个节点也就是上一组的尾节点。end当前待翻转区间的最后一个节点。初始化时pre 和 end 都指向 dummy。之后进入循环先让 end 往前走 k 步如果走不完 k 步就发现 end 为空说明剩余节点不足 k 个直接终止循环。提示end 初始指向 dummy 而不是 head是为了让“区间定位”这个动作在逻辑上保持一致。第一次循环时dummy 就是“上一组的尾节点”非常自然。2.2 翻转区间的精确定位假设当前状态如下pre 指向上一组尾节点end 从 pre 的位置出发走了 k 步之后指向当前组的最后一个节点。这时候需要记下几个关键节点start pre.next这是当前组的头节点也就是待翻转区间的起点。next end.next这是下一组的头节点翻转完成后需要把当前组接回这里。接下来把 end.next 暂时置为 null。这一步很重要把当前这一组从整个链表里“剪”下来变成一个独立的子链表。这样你调用反转函数时函数的终止条件cur为空就能正常工作不会把后面还没处理的节点一起反转进去。剪下来之后对以 start 为头的子链表调用反转函数。反转后start 变成了子链表的尾节点而新的头是原来的 end。这时pre.next 指向新头原来的 end。start.next 指向 next把翻转后的这一组接回主链表。2.3 迭代法完整代码实现下面给出JavaScript版本的实现关键逻辑都有注释。/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val (valundefined ? 0 : val) * this.next (nextundefined ? null : next) * } */ // 反转以 head 为头节点的链表返回新头节点 const reverse (head) { let prev null; let cur head; while (cur ! null) { const next cur.next; cur.next prev; prev cur; cur next; } return prev; }; const reverseKGroup (head, k) { if (head null || k 1) return head; const dummy new ListNode(0); dummy.next head; let pre dummy; let end dummy; while (end ! null) { // 让 end 先走 k 步找到当前组的末尾 for (let i 0; i k end ! null; i) { end end.next; } // 不足 k 个跳出循环 if (end null) break; const start pre.next; const next end.next; end.next null; // 断开当前组 pre.next reverse(start); // 翻转并接回 start.next next; // start 现在是组内尾节点接上下一组 pre start; // 移动 pre 到当前组末尾 end start; // 从该位置继续找下一组 } return dummy.next; };这段代码第一次看可能会觉得“end start”有点怪。我解释一下翻转完成后start 已经是当前组的最后一个节点了它就是下一组的前驱节点。所以 pre 和 end 都从 start 继续出发寻找下一组。这一步很容易写错很多人会写成 end pre.next那就跳过了下一组直接死循环了。2.4 复杂度分析为什么迭代法是面试最优解时间复杂度方面我们每个节点都被访问常数次一次是 end 在找区间时经过一次是反转时经过。整体是 O(n)n 为链表长度这没有悬念。空间复杂度方面迭代法只使用了几个临时指针变量没有额外依赖链表的长度所以是 O(1)。递归法由于递归调用栈的存在空间复杂度是 O(n/k)。虽然力扣上两种都能过但面试时如果你主动提到“迭代法能做到 O(1) 空间”会是一个不错的加分项。3. 另一种思路递归解法与取舍分析3.1 递归的设计思路迭代法已经能解决这道题为什么还要学递归因为递归的思考方式更接近人类的直觉我只需要处理“当前这一组”剩下的交给递归函数。递归版的核心逻辑可以这样描述从 head 出发找到第 k 个节点记为 tail。如果走不到第 k 个节点直接返回 head因为剩余节点不足 k 个保持原样。保存 tail.next记为 nextGroup。将 tail.next 置为 null让 head 到 tail 这一段成为一个独立子链表。反转这段子链表得到新的头节点 newHead。head.next reverseKGroup(nextGroup, k)也就是把这一段反转后的尾节点接到下一组递归处理后的结果上。返回 newHead。写法上需要注意递归终止条件是“剩余节点不足 k 个”这意味着每层递归进入时都要先去数一下是否有 k 个节点。3.2 递归版完整代码实现const reverseKGroup (head, k) { // 数一下是否有 k 个节点 let tail head; for (let i 0; i k; i) { if (tail null) return head; // 不足 k 个保持原样 tail tail.next; } // 到这里tail 指向第 k1 个节点当前组的末尾的下一个 // 需要反转的是 head 到 tail 之前的部分 // 先把这段独立出来 const nextGroup tail; tail head; let prev null; let cur head; while (cur ! nextGroup) { const next cur.next; cur.next prev; prev cur; cur next; } // 此时 prev 是反转后的新头head 变成了尾节点 head.next reverseKGroup(nextGroup, k); return prev; };注意一个细节循环条件是cur ! nextGroup而不是常规的cur ! null。因为我们只需要反转从 head 到 nextGroup 之前这一段不能动后面的节点。递归版代码很短但它会让人困惑的地方在于到底谁是新头谁是尾节点以及 head.next 接的是什么。我在本地跑了几个用例之后才彻底理顺。3.3 两种解法对比什么时候用哪个我整理了一下迭代和递归的对比方便你根据场景选择维度迭代法递归法空间复杂度O(1)O(n/k)代码长度较长变量多容易绕晕较短结构清晰理解难度指针多但控制流是线性的递归调用需要理解递推关系面试推荐度稳妥适合手撕思路优雅但容易在边界上出错我个人建议如果时间紧张优先把迭代法练到能闭眼写出来。递归法可以作为理解上的补充不用死磕。不过有一种情况例外——如果面试官明确问你“能不能用递归实现”你得能接住。4. 实操过程从暴力推导到代码落地4.1 手动画图推导一次完整流程我在学习这题时最大的收获就是“不要脑补要画图”。拿 1-2-3-4-5k2 来走一遍初始dummy - 1 - 2 - 3 - 4 - 5pre 和 end 都指向 dummy。第一轮end 走2步从 dummy 到 2。start 1next 3。断开 end.next也就是让 2.next null得到 1-2 和 3-4-5。反转 1-2得到 2-1。pre.next 2start.next 3此时链表为 dummy - 2 - 1 - 3 - 4 - 5。pre start 1end start 1。第二轮end 从 1 走2步到 4。start 3next 5。断开 4.next null得到 3-4 和 5。反转 3-4得到 4-3。pre.next 4start.next 5此时链表为 dummy - 2 - 1 - 4 - 3 - 5。pre start 3end start 3。第三轮end 从 3 走2步第一步到5第二步 end.next 为 nullend null。跳出循环。最终返回 dummy.next也就是 2-1-4-3-5。跟预期一致。这个过程我在纸上画了不下五遍每次画完都对指针关系更清晰。建议你也动手画一次别只在脑子里转。4.2 如何写出一份可读性高的题解代码有些朋友可能发现网上有些代码很短甚至十几行就能写完。但短代码不一定是好代码尤其在面试里你能不能用清晰的变量名把思路讲明白更重要。我写这题时给自己定了三条规范反转函数单独抽出来复用reverse。主流程只负责分段和拼接不要让反转逻辑混进来。变量名用能表达语义的比如start、end、nextGroup而不是p1、p2、p3。每个关键操作节点配一行注释。比如“断开当前组”“接回下一组”让阅读者能跟着注释走。这三条做下来即使一段时间后再回看这段代码也能很快想起来当时是怎么想的。刷题不是一锤子买卖要想着以后复习。注意有些人会在迭代版里把end初始化为head然后循环里做特殊判断。这个方法也能跑通但逻辑上不够统一容易漏掉头节点变化的场景。我在实际对比后还是觉得 dummy pre/end 都指向 dummy 的写法最稳。5. 常见问题与调试心得5.1 容易踩的3个大坑这题的错误模式很集中我总结了三类是我自己以及身边朋友反复踩过的反转后忘记接回原链表。由于先断开了end.next反转完后如果忘了让最开始的start.next指向next链表后半截就丢了。pre 和 end 的更新顺序写错。在迭代版里必须让 pre 先指向当前组的旧头反转后变成了尾节点再让 end 从新的 pre 出发。很多人会写成 end pre.next直接跳过了下一组。递归版里数节点时把tail tail.next多走了一步。数 k 个节点时循环结束后 tail 应该指向第 k1 个节点很多人会在这里搞混导致递归时处理的区间少了一个节点或多了一个节点。5.2 调试手法肉眼定位指针错误链表题调试最痛苦的是报错往往只告诉你“运行时错误”或者超时你根本不知道是哪个指针错了。我的做法是在关键节点打印整个链表。比如在每次循环结束时打印当前链表看看是否与预期一致。如果发现某一轮开始链表就断了或成环了就能很快锁定问题出在这一轮的操作。在本地写代码时我还会额外写一个辅助函数const printList (head) { const res []; let cur head; let count 0; while (cur ! null count 20) { res.push(cur.val); cur cur.next; count; } console.log(res.join( - )); };count 上限设为20是为了防止链表成环时死循环打爆控制台。这个函数在调试几乎所有链表题时都很有用。5.3 一道相关题k2 时的特例这道题和 LeetCode 24两两交换链表中的节点是高度相关的。当 k2 时本题就退化成了“每两个节点一组翻转”也就是第24题的场景。我建议你先去把第24题做一遍再来做这题。因为第24题不需要考虑“不足 k 个保持原样”这个条件指针数量也少一些拿来热身很合适。等你能熟练写出第24题再来挑战这题会顺很多。另外反转整个链表LeetCode 206也是绝对的前置基础。如果你发现自己写本题时频繁在反转部分卡壳说明基础还不牢先回去刷两道反转链表的热身题再说。5.4 力扣刷题攻略层面的建议hot100 是很多人刷题的主线但我不建议一上来就死磕困难题。链表专题这种强调“手感和细节”的题型更值得用“重复练习”的方式吃透。K个一组翻转链表这题我在一周内刷了三遍第一遍看着题解写第二遍合上书自己写第三遍限时10分钟手写核心逻辑。三轮之后我在面试里遇到类似题目基本不再发怵。对于准备面试的朋友我的建议是不要满足于“能过用例”要能边写边讲出每一步在做什么、为什么这么做。面试官很看重你写代码时是否思路清晰这题就是一个很好的考察点。最后分享一个我自己的小习惯每次刷完链表中“K个一组翻转链表”这种强指针操作的题我都会在第二天用一张白纸重新默写一遍核心代码。这种主动回忆比当天重复写十遍都有效。如果你也卡在这题的指针迷宫里不妨试试这个方法把画图的功夫做足指针关系理顺了代码自然就写得出来。