K个一组翻转链表：递归+迭代模板与边界避坑指南

第一次在热题榜上看到“K 个一组翻转链表”的时候我是有点发怵的。反转链表是 easy区间反转是 medium怎么加了一个“K 个一组”直接蹦到 hard 了等我真的把它做明白才反应过来这道题根本不是在考什么高深的算法思想它考的是你对链表指针的掌控力、对边界条件的直觉以及在多步操作里让链表不断链、不成环的能力。它也是 hot100 榜单里的熟面孔很多公司的算法面试都爱从它或者它的变形题切入。这篇文章我会按我自己的学习路径来写先把题目拆到不能再拆再把最关键的区间反转模板讲透然后分别给递归和迭代两种解法最后把我在这个过程中踩过的坑和面试时被追问过的问题一并整理出来。无论你是刚开始刷链表还是想把这题从“碰运气写对”变成“稳定一次写对”这篇应该都能帮到你。1. 这道 hard 题到底在考什么1.1 先把这个题目还原清楚题目给你一个单链表的头节点head和一个正整数K。你需要在链表中每 K 个节点一组把组内节点顺序翻转如果链表最后剩余的节点数量不足 K 个这部分保持原样不翻转。你不能把节点的val改了来偷懒必须真的去调整节点的next指针。结果返回调整后的链表头节点。举个例子。链表是1 - 2 - 3 - 4 - 5K 2 时结果是2 - 1 - 4 - 3 - 5。前两组两个两个翻转最后只剩一个 5保持不动。K 3 时结果是3 - 2 - 1 - 4 - 5。前三一组翻转后两个不足三个保持原顺序。链表节点的标准定义在 LeetCode 里一般是这样的我习惯用 Java 写在其他语言里只是语法差别public class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val val; } ListNode(int val, ListNode next) { this.val val; this.next next; } }1.2 hard 的来源不是算法是状态维护我先说结论这道题涉及的算法能力顶多算一个“区间反转”真正让它变成 hard 的原因是把三个动作揉在一起时容易出现状态错乱。做这道题你其实只需要三件事定位从某个起点开始走 K 步找到这一组的范围。反转把这个范围内的节点顺序掉个头。重连把反转后的组和前一组的尾部、后一组的头部都接好。第一步你不会错第二步如果你单独写也不会错。第三步看别人代码觉得非常简单自己一写就发现到处都是坑指针指向了已经被反转过的节点、记错了前一组的尾巴、这组反转完 gap 没接上、下一轮的起点定错了。所以我建议别急着背完整代码先把“区间反转”这个底座练成肌肉记忆再来看这道题整条思路会顺很多。它也是把链表题“从 easy 到 medium 再到 hard”分层递进的一个典型样本吃透它链表类问题的整体手感都会上一个台阶。2. 动手前必须吃透的区间反转模板2.1 最基础的反转三指针如果你已经完全会反转整条链表可以跳过这段。如果不熟我建议花十分钟重新写一遍这个private ListNode reverse(ListNode head) { ListNode pre null; ListNode cur head; while (cur ! null) { ListNode next cur.next; // 先保存下一个节点不然改指针后就找不到了 cur.next pre; // 当前节点指向前一个节点 pre cur; // 前一个节点移动到当前 cur next; // 当前节点移动到原下一个 } return pre; // 结束时 pre 就是新链表的头 }这段代码本质上就是一句话每轮循环里先把下一个节点攥在手里再掰断当前这个节点的 next让它指向 pre然后两个指针整体前移一格。你可以把它想象成拿着一串珠子逐个把珠子的朝向掉个头。这个过程中最容易写错的地方是cur.next被覆盖之后如果不提前把next cur.next存下来后面就找不到原链表的下一个节点了。很多链表题的崩溃都源于这个小小的顺序问题。2.2 更实用的写法反转 [a, b) 左闭右开区间反转整条链表在单独做的时候没有问题但在“K 个一组翻转”里我们几乎总是需要只翻某一小段而不是从头翻到尾。这时候我更推荐另一个模板反转从 a 开始、到 b 之前为止的区间也就是左闭右开区间 [a, b)。private ListNode reverse(ListNode a, ListNode b) { ListNode pre null; ListNode cur a; while (cur ! b) { // 注意边界条件没到 b 就继续 ListNode next cur.next; cur.next pre; pre cur; cur next; } return pre; // 返回新区间的头节点 }这段代码和反转整个链表唯一的区别就是把while (cur ! null)换成了while (cur ! b)。b 是不参与反转的第一个节点它可以是 null也可以是某个真实节点。这个写法好在哪好就好在它天然定义了反转的边界你不用先去把 b 的 next 断开反转函数自己就知道在哪里停下来。在后面递归解法里这个特性会让代码写得很干净。我强烈建议你花一下午把这个模板练到不假思索因为它能解决的不只是这一道题像“反转链表 II”这种区间反转题你也能直接套。3. 递归解法每组自己翻完再接下一组3.1 递归的三个核心步骤递归解法的思维非常直接我不管后面有几组我先把眼前这一组翻好翻好之后把“组尾”接到“后面那一堆处理完的结果”上剩下的交给递归。具体步骤拆开讲第一步从 head 出发走 K 步。如果走不完中途遇到 null说明当前这一组不足 K 个直接返回 head保持原样不翻转。第二步如果走满了 K 步那么指针指向的是第 K1 个节点。我们把[head, 这个节点)区间反转单次反转的返回值就是反转后这组的新头。第三步当前这一组的旧头 head 反转完变成了组尾它应该指向下一组翻转后的结果。所以写head.next reverseKGroup(node, k)其中 node 正好就是第 K1 个节点。最后返回第二步得到的新头。3.2 Java 和 Python 的代码实现Java 版本class Solution { public ListNode reverseKGroup(ListNode head, int k) { if (head null) return null; ListNode node head; for (int i 0; i k; i) { if (node null) return head; // 不足 k 个保持原样 node node.next; } ListNode newHead reverse(head, node); // 反转本组 head.next reverseKGroup(node, k); // 本组组尾接上下一组的结果 return newHead; } private ListNode reverse(ListNode a, ListNode b) { ListNode pre null; ListNode cur a; while (cur ! b) { ListNode next cur.next; cur.next pre; pre cur; cur next; } return pre; } }Python 版本from typing import Optional class Solution: def reverseKGroup(self, head: Optional[ListNode], k: int) - Optional[ListNode]: if not head: return None node head for _ in range(k): if not node: return head node node.next new_head self.reverse(head, node) head.next self.reverseKGroup(node, k) return new_head def reverse(self, a: Optional[ListNode], b: Optional[ListNode]) - Optional[ListNode]: pre None cur a while cur ! b: nxt cur.next cur.next pre pre cur cur nxt return pre你会发现两种语言的思路完全一样。其实这类链表题真正重要的就是思路和边界语言只是换了层皮。3.3 用一个小例子推演递归的调用我们拿1 - 2 - 3 - 4 - 5K 2 来推一遍。最外层调用reverseKGroup(1 节点, 2)node 从 1 出发走两步到达 3。先执行reverse(1, 3)把1 - 2反成2 - 1返回新头 2。然后执行1.next reverseKGroup(3 节点, 2)。进入第二层递归参数是 3 节点再走两步node 到达 5。执行reverse(3, 5)把3 - 4反成4 - 3返回新头 4。然后执行3.next reverseKGroup(5 节点, 2)。进入第三层递归参数是 5 节点node 从 5 出发走一步就到 null不足两步直接返回 head也就是返回 5。回到第二层3.next 接上 5所以这层翻转完的结果是4 - 3 - 5返回新头 4。回到最外层1.next 接上 4所以整体结果就是2 - 1 - 4 - 3 - 5。整个过程的关键是递归函数返回的永远是这一组翻转后的新头上层只需要把这个新头接到自己组尾的 next 上。理解这一点递归解法就不可能写乱。3.4 递归的空间开销递归解法的时间复杂度是 O(n)n 是链表长度因为每个节点最多被访问常数次。空间复杂度是 O(n/k)递归深度取决于有多少组每一层方法调用都会占用栈空间。如果链表特别长、K 又小递归栈会比较深。如果你的面试官特别在意空间他大概率会追问“能不能改成 O(1) 空间”这时候就该切到迭代解法了。4. 迭代解法用 dummy 节点一遍穿好所有组4.1 为什么需要一个 dummy 节点迭代解法里有一个几乎所有标准答案都会用的技巧在头节点前面放一个虚拟节点 dummy。为什么需要它因为第一组被翻转后原来的 head 就不在链表头部了新的头部是翻转后的那个节点。如果不搞 dummy你写代码时每个地方都要特判“现在是不是第一组”异常啰嗦。有了 dummy 之后它始终是整条链表的“锚点”。无论谁被翻到最前面dummy.next一定指向最终链表的头你只需要在程序最后返回dummy.next就行。这也是“用空间换代码统一性”的典型例子多一个节点换来回逻辑完全同构。4.2 迭代解法的完整步骤迭代的思路是用 pre 记录“上一组的末尾节点”start 记录“本组的第一个节点”end 用来扫描定位“本组的最后一个节点”。在每一轮循环里从 pre 开始走 K 步看能不能走到一个真实节点。如果走不动了说明最后不足 K 个直接返回结果。如果够一组记录nextStart end.next也就是下一组的开头。反转[start, nextStart)这一区间拿到本组新头 newHead。让pre.next指向 newHead让本组旧头start的 next 指向 nextStart重新把链表串起来。更新pre start此时 start 已经变成这组的末尾start nextStart进入下一组。把代码写出来class Solution { public ListNode reverseKGroup(ListNode head, int k) { ListNode dummy new ListNode(0); dummy.next head; ListNode pre dummy; while (true) { ListNode end pre; for (int i 0; i k; i) { end end.next; if (end null) { return dummy.next; // 剩余不足 k 个 } } ListNode start pre.next; ListNode nextStart end.next; ListNode newHead reverse(start, nextStart); // 反转本组 pre.next newHead; // 上一组末尾接上本组新头 start.next nextStart; // 本组新尾接上下一组开头 pre start; // 下一轮的 pre 是这组末尾 } } private ListNode reverse(ListNode a, ListNode b) { ListNode pre null; ListNode cur a; while (cur ! b) { ListNode next cur.next; cur.next pre; pre cur; cur next; } return pre; } }这里用的reverse(start, nextStart)是左闭右开区间反转所以不需要把end.next置成 nullreverse 函数自己会在到达 nextStart 前停下来。反转完之后再通过start.next nextStart把断掉的地方接回去。4.3 另一种常见写法先断开再反转网上很多题解用的是另一种风格在反转之前先把end.next置空把它临时变成一条独立的短链表然后直接调用reverse(head)反转整个链表。原理和我这个版本完全一致只是反转函数用的边界写法不同。你选哪种都可以但一旦定了一种就不要混着写。我见过不少同学先把end.next断开了又用左闭右开反转函数自己把自己搞糊涂。一个解题模板多用几遍形成习惯之后再提速才有意义。5. 边界条件与高频踩坑实录5.1 不足 K 个的情况两种解法的处理递归解法在走 K 步的过程中一旦发现 node 为空就直接返回 head。这意味着当前这一段不足一组原封不动返回给上层上层自然把它接在上一个组的后面。迭代解法是在扫描 end 的时候发现端倪如果走不完 K 步就撞上 null说明从当前 pre 后面开始已经不足 K 个此时函数直接返回dummy.next。注意这里不能再继续反转了否则会把末尾不足一组的节点也翻掉。两种做法的触发点不一样但结果一致末尾不满一组时保持原顺序。5.2 三个我最容易犯的错我先说错误再给修正希望你写的时候能躲开。第一个坑忘了重新接start.next。反转结束后start 是组尾它的 next 指向的是反转过程中生成的 null如果你不显式写start.next nextStart这组和下一组之间就断了。很多人在递归解法里没这个问题因为递归天然用head.next reverseKGroup(node, k)保证连接但迭代解法里漏掉这行几乎是必犯错误。第二个坑确定一组范围时 end 的初始位置错了。正确写法是让 end 从 pre 出发走 K 步这样 start 和 end 之间的节点数量刚好是 K 个。如果你让 end 从 start 出发走 K 步走到的是第 K1 个节点等于把下一组的头也算进这一组了翻转范围直接错掉。第三个坑更新下一轮起点时顺序不对。下一轮的 pre 应该是当前组的旧头 start翻转完之后它就是组尾下一轮的 start 应该是记录的 nextStart。如果你先改了start nextStart再回头用 start 去指 pre这一轮就白写了。写代码的时候建议严格按“先记录、再重连、最后更新”的顺序来。5.3 自测时的常用手段链表题最烦的一点是“看起来对跑起来崩”我自测时靠的就是两个小工具。第一个工具是数组转链表方便快速构造用例private ListNode buildList(int[] nums) { ListNode dummy new ListNode(0); ListNode cur dummy; for (int num : nums) { cur.next new ListNode(num); cur cur.next; } return dummy.next; }第二个工具是打印链表最好在 while 循环里加一个计数器超过一定次数直接报错防止死循环把程序挂死private void printList(ListNode head) { ListNode cur head; int count 0; while (cur ! null) { System.out.print(cur.val - ); cur cur.next; if (count 20) { // 防死循环 System.out.println(可能有环终止打印); return; } } System.out.println(null); }构造用例的时候一定要覆盖这几种组合我列成表方便你自查用例K预期行为空链表任意返回 null单节点 11返回 1单节点 12返回 1不足一组不翻转1 - 222 - 1正好一组1 - 2 - 322 - 1 - 3末尾不足1 - 2 - 3 - 422 - 1 - 4 - 3正好整除1 - 2 - 3 - 4 - 533 - 2 - 1 - 4 - 5我统计过周围人在这题上栽跟头的场景90% 都落在这几种组合里。6. 从刷题到工作这道题背后的思想复用6.1 分组反转思想在真实项目里并不少见很多人觉得链表 hard 题除了面试毫无用处其实“按固定大小分组逐组处理后拼接”这个模式在真实系统里出现频率挺高的。举几个例子。消息队列做批量重排或协议组装时经常有“每 N 条消息组成一批批内反转或重新排列后写出”的需求数据分页处理时每一页内部的顺序调整、页与页之间要保持连接和这道题的分组重连思路如出一辙。链表的双向结构、前驱后继指针在内存分配器、文件系统块管理、事件循环的任务队列里也到处都是。当然你不能直接照搬 LeetCode 的链表实现但“先定位边界再局部处理最后重连”这个三段式思路是可以内化成一种工程直觉的。6.2 面试延伸问题怎么答围绕这道题面试官一般还会追加几个问题我提前帮你整理一下。第一个追问时间复杂度是多少能不能优化答案是 O(n)每个节点在分组扫描里最多被访问常数次反转阶段也只被访问常数次整体是线性。优化空间不大但你可以指出扫描和反转可以在统一循环里合并省掉一点常数时间。第二个追问空间复杂度递归是 O(n/k)迭代是 O(1)。所以如果面试官要求“不要递归”本质是希望你实现迭代版本。第三个追问能不能用数组先存下来再改写指针可以但这不是链表题的本意。先把节点收集到数组翻转 index再回填 next时间 O(n) 空间 O(n)写法上确实简单。但这样一来面试官想考察的指针操作和边界控制就全部落空了。数组法可以作为兜底方案但能写指针操作还是要写。6.3 我的刷题体会最后说一点个人体会。这题我前后刷了三遍才到“闭眼能写”的程度。第一遍死在区间反转的边界上第二遍栽在迭代里忘记重接start.next第三遍终于能稳定写出无 bug 的版本。后来我形成了一个习惯凡是链表 hard 题都先想办法抽象成“重复的小步骤”把小步骤写成一个独立函数再在主体里调度它。这个方法我一直在用包括这道“K 个一组翻转链表”。如果你正在准备算法面试建议把这题放在“反转链表 II”之后刷把区间反转基本功练好再上 hard会顺利得多。刷完之后顺手把“每 K 个一组反转”的变形题拿出来对比一下形成自己的链表题方法论比单纯背答案有用得多。