题目“K 个一组翻转链表”是很多人在链表进阶路上的一道坎反转单链表人人都会但加上“每 K 个一组”这个条件之后定位、翻转、缝合三件事搅在一起稍不留神就会写出死循环。这篇文章不讲虚的直接从指针设计、组内翻转头插法、递归与迭代取舍、边界排查四个角度拆开讲最后给出变体题和时间复杂度推导希望能帮你真正把这道题吃透。1. 这道题难在哪不是反转而是边界的缝合1.1 整链反转很简单先看最基础的整链反转。给定1 - 2 - 3 - 4 - 5要得到5 - 4 - 3 - 2 - 1需要的只是三个指针prev、cur、next。遍历过程中把cur.next从指向后继改成指向前驱然后整体往后挪。代码量很短逻辑也很直白public ListNode reverseList(ListNode head) { ListNode prev null; ListNode cur head; while (cur ! null) { ListNode nxt cur.next; cur.next prev; prev cur; cur nxt; } return prev; }这个问题的本质是链表的每个节点只有一个后继你要做的就是把这个“后继指向”全部反转。一旦理解了这一步整链反转基本没有困难。1.2 K 个一组带来了什么额外复杂度但是“K 个一组翻转链表”完全不是上面这件事的简单重复。以1 - 2 - 3 - 4 - 5 - 6 - 7、K3 为例期望结果是3 - 2 - 1 - 6 - 5 - 4 - 7。也就是说你要把原始链表切成若干段每段内部做反转段与段之间还要保持原来的顺序。这带来几个整链反转里不存在的难题你需要先定位第 K 个节点在哪也就是给每组找边界反转之后原组的尾节点变成了新组的头节点需要接上上一组的尾原组的头节点变成了新组的尾节点需要接上下一组的头如果最后一组不足 K 个要保持原顺序不翻转头节点可能发生变化不能再简单用一个head做返回入口。所以这道题考的其实是“在指针局部变化时如何维护整条链的结构”。它不是反转问题而是边界缝合问题。维度整链反转K 个一组翻转操作单元整条链若干个独立组指针数量3 个通常 4 个以上头节点是否变化会但只需返回最后一个节点会且需要虚拟头节点统一处理边界条件基本只有 null 判断空链表、K1、剩余不足 K 个等核心难点反转指针定位、反转、拼接三者组合1.3 面试官真正想看到的我参加过不少算法面试也帮别人模拟过面试。说实话候选人能写出完整反转链表的人很多但能在白板上把“K 个一组翻转链表”优雅写出来的人比例不高。面试官要看的核心就三点第一遇到头节点可能变化的链表知不知道用虚拟头节点第二能否在动手前想清楚每一组的前驱、组头、组尾是谁第三能不能处理“剩余不足 K 个保持原序”这类边界。这三点恰恰是这道题设计出来要考的。它表面考反转实际考的是边界意识和结构感知力。2. 动手之前先把指针布局画清楚2.1 为什么需要一个虚拟头节点很多人在写这道题时会卡在一个地方第一组翻转之后链表的头节点变了那最后该返回谁如果不用虚拟头节点你就得单独拿一个变量保存翻转后的真实头节点或者每翻完一组就去更新一次head很容易出错。更优雅的做法是在真正头节点前面加一个dummy节点所有组都按照“组前节点pre的下一个节点开始到groupTail结束”来处理第一组和非第一组的逻辑完全一致。因为dummy.next会在第一组翻转完成后自动指向新的头节点最后直接返回dummy.next即可。这个技巧在涉及头节点变化的链表题里几乎是万能的。2.2 四个关键引用的分工写代码之前建议先把以下四个引用的职责写清楚。我最初的几次实现用了很随意的变量名结果每次 debug 都得重新推演非常痛苦。引用位置作用dummy真实头节点之前统一处理头节点变化最终返回入口pre当前组的前一个节点反转后组首需要接到 pre 后面groupHead当前组的第一个节点反转前组首反转后变成组尾groupTail当前组的最后一个节点反转前组尾反转后变成组首nextGroup下一组的第一个节点必须提前保存否则指针一变就找不回每一轮开始时pre是已知的。groupHead不需要额外计算直接取pre.next就是当前组的第一个节点。groupTail则需要从pre出发向后走 K 步找到本组最后一个节点。nextGroup是groupTail.next必须在翻转前保存。2.3 定位组尾的边界判断细节定位groupTail的代码不难写但有一个很多人容易忽略的细节判断不足 K 个的逻辑必须放在循环里面。ListNode groupTail pre; for (int i 0; i k; i) { groupTail groupTail.next; if (groupTail null) { return dummy.next; } }为什么不能先把 groupTail 挪 K 步循环结束后再判断因为如果剩余节点不足 K 个走到第 K 步时groupTail已经变成 null此时再在后面访问groupTail.next就会空指针异常。放在循环内部每次移动后立刻检查一旦为 null 就直接返回dummy.next保持了剩余部分的原序。还有一个细节值得注意当前组恰好剩余 K 个节点时第 K 步走完后groupTail指向的是这一组的最后一个节点它不是 null。也就是说判断条件只看groupTail null就够了不用担心“刚好够一组”被误判为不足。3. 组内翻转的两种实现头插法与切断接回法3.1 头插法摘节点搬到组前头插法是我个人最推荐的写法。它的思路非常朴素不让groupHead移动反复把它后面的节点摘下来插到pre的后面。每插一个原来靠前的节点就被“挤”到更后面。循环 K-1 次整组就反转过来了。public ListNode reverseKGroup(ListNode head, int k) { if (head null || k 1) { return head; } ListNode dummy new ListNode(0); dummy.next head; ListNode pre dummy; while (true) { ListNode groupHead pre.next; ListNode groupTail pre; for (int i 0; i k; i) { groupTail groupTail.next; if (groupTail null) { return dummy.next; } } // 头插法把 groupHead 后面的节点逐个搬到 pre 后面 for (int i 1; i k; i) { ListNode move groupHead.next; groupHead.next move.next; move.next pre.next; pre.next move; } pre groupHead; } }推演一下。假设当前状态是pre - 1 - 2 - 3 - 4K4第一次把 2 摘出来插到 pre 后pre - 2 - 1 - 3 - 4第二次把 3 摘出来插到 pre 后pre - 3 - 2 - 1 - 4第三次把 4 摘出来插到 pre 后pre - 4 - 3 - 2 - 1这里的关键是每次摘的都是groupHead.next而不是pre.next。如果搞混了链表会在第一步就变成环。我第一次写的时候就犯了这个错想着“把后面的节点搬到前面”就直接拿cur.next结果链表从第 2 个节点开始自动绕圈debug 了很久才发现必须通过groupHead.next来摘节点。另一个容易错的地方是循环次数。一组有 K 个节点只需要移动 K-1 次。因为groupHead本身不需要移动它最后会自然成为组的最后一个节点。3.2 切断接回法不想动脑时的稳妥方案如果你在面试时一时想不到优雅的头插法可以用切断接回法保底。思路是先把这一组的尾部断开让组内链表变成独立的短链表然后用标准三指针反转最后再接回去。public ListNode reverseKGroup(ListNode head, int k) { if (head null || k 1) { return head; } ListNode dummy new ListNode(0); dummy.next head; ListNode pre dummy; while (true) { ListNode groupHead pre.next; ListNode groupTail pre; for (int i 0; i k; i) { groupTail groupTail.next; if (groupTail null) { return dummy.next; } } ListNode nextGroup groupTail.next; groupTail.next null; // 反转 groupHead 到 groupTail 的独立短链表 ListNode prev null; ListNode cur groupHead; while (cur ! null) { ListNode nxt cur.next; cur.next prev; prev cur; cur nxt; } // 接回原链 pre.next prev; groupHead.next nextGroup; pre groupHead; } }这段代码的逻辑层次更清楚断开、反转、接回。缺点是需要手动恢复断掉的groupTail.next。如果忘了groupHead.next nextGroup整条链表会从 groupHead 处断成两截下一轮遍历直接死在空指针上。3.3 为什么建议先写切断接回再优化我的习惯是面试场上先写切断接回版本。它每一步都对应一个直观动作不容易出低级错误。跑通之后再告诉面试官“这里其实可以用头插法把临时断链这个动作省掉”然后补充头插法的实现这会让人觉得你是真的理解而不是死记硬背。实际刷题时两种方法都值得自己完整写三遍尤其是要能徒手推演头插法的每一轮指针变化。很多资料只给最终代码不讲为什么每次摘的是groupHead.next这会让初学者卡很久。4. 四类边界场景与指针 BUG 的排查链路4.1 空链表、单节点、K1 的处理空链表很好处理直接返回 head 即可。单节点且 K 大于 1 的情况在定位 groupTail 时会发现剩余的 1 个节点不足 K于是提前返回同样不额外写特殊分支。需要注意的其实是 K1。从语义上讲每 1 个节点一组翻转结果等同于原链表。我的第一版代码没有加k 1的判断结果在 K1 时头插法的 K-1 次循环不执行pre 不断地被更新为 groupHead最终行为也能正确。但如果切断接回法里的反转逻辑被触发反而会把不需要反转的链表反转一遍结果就不对了。所以稳妥做法是在函数开头直接写if (head null || k 1) { return head; }既省了不必要的逻辑也让后续代码的循环条件更干净。4.2 剩余不足 K 个时保持原序这里的“保持原序”是在定位 groupTail 阶段就决定的。一旦发现groupTail null说明从当前组开始往后剩余节点数小于 K不能构成一组。此时直接返回dummy.next。我见过有人写if (groupTail null) break;然后在循环外处理返回这样也可以但容易把真正的返回条件和循环结束条件混淆。直接return dummy.next最干脆因为不管后面有多少段前面已经翻转完成的组都已经正确接好剩余部分保持原序就是最终答案。4.3 翻完一组后 pre 更新错位的问题最容易踩的坑是翻转完一组之后不知道该把 pre 指向哪里。注意pre的含义是“下一组的前驱节点”也就是当前组的最后一个节点。在当前组被反转之后最后一个节点恰好是原来的groupHead。头插法的代码中groupHead.next会在最后一次迭代中被更新为下一组的起始节点所以直接pre groupHead即可。切断接回法中groupHead在反转后也变成了组尾同样应该把pre更新为groupHead。我见过不少人的代码在这里把pre写成了pre.next或者groupTail。如果写成pre.next下一轮循环就拿不到下一组的第一个节点链表会越翻越乱如果写成groupTailgroupTail 在反转之前是组尾修改后会被接到 pre 后面位置就漂移了。用变量名想清楚职责能避免这类低级错误。4.4 调试方法小数据加手动画表链表题最有效的调试方法是用小规模数据手动推演。以1 - 2 - 3 - 4 - 5、K2 为例翻转过程如下轮次pregroupHeadgroupTail翻转后链表1dummy122 - 1 - 3 - 4 - 521342 - 1 - 4 - 3 - 5335定位时 tail 为 null返回 2 - 1 - 4 - 3 - 5这种表我每次讲题都会画一遍既快又不容易出错。实际操作时可以在循环里加打印输出每一轮翻转后链表的样子。用 5 个节点的测试数据足够发现 90% 的 off-by-one 问题尤其是“翻转 K-1 次还是 K 次”这种经典陷阱。如果你发现链表成环把测试数据换成一个更小的链表比如1 - 2 - 3、K2然后用笔纸逐步推演一般 10 分钟内能找到指针错乱的位置。我一直觉得链表题修炼到最后拼的就是“能不能在纸上画出指针变化”。5. 递归写法与迭代写法的取舍5.1 递归版在做什么迭代写法的思路是从左往右一组一组翻。递归写法的思路则正相反先递归处理后面的组拿到nextHead再把当前组的 K 个节点逐个翻到nextHead前面。public ListNode reverseKGroup(ListNode head, int k) { ListNode tail head; int count 0; while (count k tail ! null) { tail tail.next; count; } if (count k) { return head; } ListNode nextHead reverseKGroup(tail, k); ListNode prev nextHead; ListNode cur head; for (int i 0; i k; i) { ListNode nxt cur.next; cur.next prev; prev cur; cur nxt; } return prev; }注意这里的tail从head开始走 K 步最终指向第 K1 个节点也就是下一组的起始点。递归调用处理的就是从tail开始的剩余链表。拿到nextHead之后把当前组的 K 个节点按头插方式放到nextHead前面循环结束后返回的prev就是当前组的新组头。这种写法不需要 dummy 节点也省去了手动维护pre的麻烦。理解递归关键在于每次调用只负责“当前这一组”后面的组我已经假定递归函数处理好了。5.2 递归的空间代价和面试取舍递归版本的代码更短思维更抽象但它有一个不可忽视的缺点需要消耗递归栈空间。假设链表有 N 个节点一组 K 个递归深度就是 N/K。K 比较小且链表很长时递归栈可能很深。比如一个百万节点的链表K2递归深度到了五十万层很容易触发栈溢出。如果面试官明确要求空间复杂度 O(1)迭代版本是唯一选择。如果面试官只是问“还能怎么写”可以先用迭代给出 O(1) 方案再补充递归版本展示对问题结构的理解。5.3 代码对拍与选择建议建议把两种实现都写出来然后用随机生成的链表互相对拍验证。写一个工具函数生成随机链表再写一个朴素解法比如借助数组倒序作为基准跑上几百组数据对比输出。这一类看似多余的测试在真实项目里也是排查逻辑问题最可靠的方式。我在学习这道题时先写递归理解了分组结构再回头用迭代实现。这个顺序比直接啃迭代版本要顺畅许多。如果你卡在迭代的指针维护上不妨先用递归把“组”的概念建立起来。6. 复杂度证明、变体题与刷题收尾建议6.1 为什么总体是 O(n)先算时间。定位每一组的groupTail需要向后走 K 步组数是 N/K所以定位总开销是 K × (N/K) O(N)。头插法里每组需要移动 K-1 次总开销是 (K-1) × (N/K) ≈ O(N)。每一组的额外操作都是常数级别因此整体时间复杂度是 O(N)。再算空间。迭代版本只用到了常数个指针变量空间复杂度 O(1)。递归版本因为有调用栈空间复杂度为 O(N/K)更粗略地讲也属于 O(N)。这个结论意味着无论 K 取多大你都不需要额外数组来辅助翻转原地就能完成。这也是这道题被称为“链表题进阶必修”的原因之一。6.2 一个核心思想能带出的变体题掌握这道题之后很多链表问题会变得顺手K2 的特例就是“两两交换链表中的节点”定位逻辑甚至更简单“反转链表指定区间”本质上就是在这里找到区间边界后做一次局部反转“回文链表判断”可以先找到中点翻转后半段再逐一比对“每 K 个节点逆序输出但不修改链表”可以走一遍递归的逆序思路。这些题看起来各不相同但核心都一样先把链表拆成可控的小段再考虑翻转或拼接。刷题的时候不要只背代码试着找出每道题里“组”的边界在哪、“连接点”在哪举一反三的效果会比盲目刷题好很多。6.3 画图习惯是链表题的终极解法最后分享一个我个人的习惯解任何链表题先画图。小到 5 个节点的用例大到实际项目里排查链表结构问题我都会先画出当前指针指向再标出每一轮之后的变化。原因很简单链表的操作本质是改箭头而人类对“箭头”的理解比对“变量”的理解直观得多。画图的时候变量名也要起得能区分职责。我早期会用a、b、c这种缩写结果画完图自己在代码里也分不清谁是谁。后来改成dummy、pre、groupHead、groupTail、nextGroup这样语义明确的命名代码的可读性立刻上了一个台阶bug 出现的频率也低了很多。“K 个一组翻转链表”作为链表操作的集大成者很适合作为练习的试金石。如果你能独立写出迭代版、头插法、递归版并且在白板上把每一轮指针变化说清楚那么你的链表基础已经相当扎实了。剩下的就是多做题、多画图、多复盘把这种“先想指针布局再动手写”的习惯带到每一道题里去。