1. 面试官为什么爱考这道题从单链表反转到K组翻转的思维跨度在算法岗的面试里链表题几乎是开场白级别的内容。但同样是链表考反转链表和考K个一组翻转链表完全是两个维度。前者是热身后者是筛选。我见过太多候选人能流畅写出206题的递归和迭代但一遇到25题就卡在边界条件上要么死循环要么丢节点要么没处理最后不足K个的情况。为什么这道题这么有区分度因为它把三个核心能力揉在了一起局部操作链表的精确性、递归思想的抽象能力、以及处理边界情况的严谨性。你不仅要会翻转一个子链表还要知道怎么把翻转后的子链表接回去怎么处理头节点变化的特殊情况怎么判断剩余的节点够不够一组。任何一个环节掉链子代码就跑不对。这道题的通用描述是给定一个单链表的头节点 head每 K 个节点一组进行翻转返回翻转后的链表。如果剩余节点不足 K 个保持原有顺序。注意这里的 K 是正整数且 K 小于等于链表长度时才能翻转如果 K 大于链表长度那就什么都不做。我先说结论这道题没有想象中那么难但它强迫你建立虚拟头节点 子链表定位 局部翻转 重新连接的完整思维链。如果你能一次性把代码写对面试官基本默认你的链表基本功是过关的。接下来我按我自己授课和刷题时习惯的拆解路径把这道题彻底讲透。2. 动手写代码前先把链表翻转的断、接、头三件事想明白很多人一上来就写 while 循环结果越写越乱。我建议你先在纸上画出三个子问题想清楚了再动键盘。2.1 子链表翻转三指针法的标准套路翻转一个单链表段最经典的做法就是三指针prev、curr、next。假设我们要翻转从节点 start 到节点 end 的这一段翻转后 start 变成这段的尾end 变成这段的头。如果这段之外没有其他节点那翻转后的头就是 end如果这段之外有前驱节点那前驱节点的 next 要指向 end如果这段之后有后继节点那 start 的 next 要指向原后继节点。这里有一个关键认知翻转一段子链表本质上就是逐个把节点的 next 指向前一个节点。三指针法的循环体就是暂存下一个节点 nextNode curr.next把当前节点指向 prevcurr.next prev移动指针prev currcurr nextNode循环结束后prev 就是原来的 endcurr 就是原来 end 之后的第一个节点。也就是说翻转后的子链表头是 prev尾是原来的 start而 start.next 应该接上 curr。这套逻辑我在 LeetCode 206 题里已经讲过无数遍但在 25 题里它只是局部工具你得把它封装出来反复调用而不是每次都重新思考。2.2 哑节点的价值统一头节点变化的处理单链表题里最让人头疼的往往就是头节点可能被换掉。在 K 个一组翻转里如果第一组翻转后原来的 head 变成了第二组的前驱或者整条链的中间节点那么返回值必须是新的头节点。为了统一处理业界标准做法就是设置一个虚拟头节点 dummy让 dummy.next 指向 head然后所有翻转操作都在 dummy 之后的链上进行最后返回 dummy.next。这个技巧的本质是把头节点变成普通节点这样无论第一组怎么翻转我们都不需要单独写 if 语句判断返回 head 还是返回新头。面试官看到你写 dummy基本就不会再追问头节点边界了因为这是链表题里最成熟、最稳妥的写法。2.3 定位一组的边界数出 K 个节点翻转之前得先确定这一组从哪开始、到哪结束。因为链表是单向的我们不能像数组那样直接按索引切片只能通过指针遍历计数。常见的写法是用一个指针 end 从当前组的起点开始走 K-1 步因为起点算第一个如果中途遇到 null说明剩下的节点不足 K 个那就不用翻转直接返回结果。这一步听起来简单但很多人会栽在走几步上。我习惯先写出一个小工具函数传入 start 节点和 K返回翻转后的子链表头同时把 start 之后的连接关系处理好。但在迭代解法里我们还需要记录当前组的前驱节点 pre 和下一组的起点 nextGroup。如果你在纸上画图你会发现整个流程就像一个流水线pre 指向上一组翻转后的尾巴start 是当前组的第一个节点end 是当前组的最后一个节点翻转后 start 变成当前组的尾巴end 变成当前组的头然后让 pre.next 指向 endstart.next 指向 nextGroup最后把 pre 更新为 start把 start 更新为 nextGroup。这套流程不需要背代码你只要记住四个指针pre、start、end、nextGroup。每次处理一组就做四件事定位 end、记住 nextGroup、翻转 start 到 end、接回 pre 和 nextGroup。顺序不能乱尤其是先记住 nextGroup这一步因为翻转会破坏原来 end 之后的连接如果不提前存下来后面就找不到了。3. 递归解法让函数自己处理下一组代码最短但隐藏细节递归思路非常优雅翻转前 K 个节点然后递归处理剩余的链表递归返回的结果接在刚才翻转后的尾部。换句话说reverseKGroup 函数接收一个头节点 head 和 K返回值是从 head 开始按 K 个一组翻转后的链表头。那么当 K 为 2链表为 1-2-3-4-5 时先翻转 1-2 得到 2-1然后让 1-next 指向 reverseKGroup(3-4-5) 的结果即 4-3-5最终得到 2-1-4-3-5。3.1 递归的终止条件与不足 K 个的处理递归的 base case 是如果链表长度不足 K直接返回原链表头。这个判断怎么做最直观的方式是把当前链表的后续 K 个节点数一遍如果不够 K 就返回 head。注意这里的数一遍需要用循环从 head 出发走 K 步如果中途遇到 null 就说明不够。这里有个细节必须先判断长度再翻转。如果你先翻转了前 K 个发现后面不够 K那就会把不该翻转的也翻了结果就错了。我还见过一种写法先递归再判断但那种写法会把问题复杂化而且容易在递归回溯时搞错返回引用。我建议老实使用先数后翻。3.2 递归翻转部分的实现细节递归翻转前 K 个节点可以使用上面提到的三指针法。假设当前组起点是 head我们翻转 K 个节点翻转后 newHead 是第 K 个节点head 变成了当前组的尾巴。这时将 head.next 指向递归返回的结果然后返回 newHead。伪代码大致是这样def reverseKGroup(head, k): if head is None: return None end head count 0 while count k and end is not None: end end.next count 1 if count k: return head # 此时 end 是下一组的起点不是本组的最后一个节点 # 翻转前 k 个节点从 head 到 kth kth head prev None cur head for _ in range(k): next_tmp cur.next cur.next prev prev cur cur next_tmp # prev 是翻转后的头head 是翻转后的尾 head.next reverseKGroup(end, k) return prev这里有一个特别容易踩的坑数 K 个节点时end 最终指向的是第 K1 个节点也就是下一组的起点。上面的循环结束后end 等于第 K1 个节点或者 null。很多人会以为 end 是第 K 个节点然后把翻转范围搞错。你可以这样记反转前需要先断链把 end 当作剩余部分的新头传给递归函数。递归函数会自己判断剩余部分够不够 K。3.3 递归解法的面试评价与适用场景递归代码量少逻辑链条清晰面试时如果时间紧张写出递归版是一个不错的策略。但要注意两个问题一是递归深度如果链表特别长递归深度可能达到 O(n/k)在 Java/C 里可能导致栈溢出二是递归函数中每次都要数 K 个节点这样其实有额外的遍历开销。不过在面试场景下这些都不是大问题因为面试官更看重你能否快速给出正确解法并解释清楚思路。我自己在实际面试中如果候选人先写递归我会继续追问迭代写法因为迭代写法更考验对链表引用的掌控。建议你两种都准备至少在心里能把递归版改写成迭代版。4. 迭代解法用哑节点稳扎稳打现场写代码更不容易出 bug迭代解法是我个人最推荐在面试中演示的方案。它不是最炫技的但胜在直观、可控、不容易写出隐藏 bug。核心思路就是上一节提到的四个指针流水线。4.1 完整代码拆解Python 版本先看代码再逐行解释def reverseKGroup(head, k): if not head or k 1: return head dummy ListNode(0) dummy.next head pre dummy start head while start: # 判断剩余节点是否够 k 个 end start count 1 while count k and end: end end.next count 1 if not end: break # 剩余不足 k 个保持原样 # end 现在是第 k 个节点本组最后一个 next_group end.next # 翻转 start 到 end 这段 new_start reverse_between(start, end) # 重新连接 pre.next new_start start.next next_group # 移动 pre 和 start pre start start next_group return dummy.next def reverse_between(start, end): prev None curr start while prev is not end: next_tmp curr.next curr.next prev prev curr curr next_tmp return prev # 翻转后 end 变成了头这段代码的关键点在两个地方。第一个是在判断剩余节点时我让 end 从 start 开始然后走 K-1 步循环结束后 end 指向第 K 个节点而不是第 K1 个。这跟递归版里的 end 语义完全不同递归版里 end 是下一组起点。很多人在迭代版里沿用了递归版的思考方式导致翻转的范围少了一个节点。记住迭代版里 end 是本组尾部递归版里 end 是下一组头部。写之前先明确你的 end 代表什么再写循环。第二个关键是 reverse_between 函数。这个函数里我写的循环条件是prev is not end而不是常规的curr变空。为什么因为我们只想翻转从 start 到 end 这一段end 是最后一个要翻转的节点。当 prev 恰好是 end 的时候说明我们已经处理完了最后一个节点此时 curr 指向了 next_group循环应当停止。如果写成while curr会把 next_group 里的节点也一并翻转那就出大问题了。所以这里用 end 作为终止标志是处理局部翻转的标准技巧。4.2 为什么这个模板在面试中更稳我给学员讲这道题时特别强调一个理念不要尝试在每个循环里同时做数数、翻转、连接三件事。把翻转单独抽成一个函数会让主流程非常清晰面试官一眼就能看出你的思路。而且 reverse_between 这个函数本身是通用的你可以把它用在很多链表问题上比如反转链表 II只是传参不同而已。另外迭代版的时间复杂度是 O(n)每个节点最多被访问常数次。空间复杂度是 O(1)只用了几个指针变量。面试官如果追问空间复杂度你能理直气壮地说 O(1)这比递归版本有优势因为递归隐式地使用了栈空间。我在实际编码时还习惯在 reverse_between 里加一个断言end 存在。虽然逻辑上已经保证但加上断言能防呆。不过面试场景中不需要写得这么防御性反而显得啰嗦。所以我通常只在函数开头注释说明入参条件不写 assert。4.3 用图来走一遍完整流程为了让你彻底理解我描述一遍 K3、链表为 1-2-3-4-5 的流程初始dummy-1-2-3-4-5predummystart1。第一轮end 从 1 开始走 2 步到 3。next_group4。翻转 1-2-3变成 3-2-1。此时 pre(dummy).next 指向 3start(1).next 指向 4。链表变成 dummy-3-2-1-4-5。然后 prestart(1)startnext_group(4)。第二轮start4end 从 4 开始走 2 步走到 5。next_groupnull因为 5.next 是 null。翻转 4-5变成 5-4。pre(1).next 指向 5start(4).next 指向 null。链表变成 dummy-3-2-1-5-4。pre4startnull循环结束。返回 dummy.next即 3。最终结果 3-2-1-5-4符合要求。注意第二组只有两个节点但 K3。判断条件是 end 从 start 开始走 K-12 步start4第一步到 5第二步时 end5.next 是 null循环条件while count k and end会因为 end 为空而中止此时 count2 3所以不够break。这正是最后不足 K 个保持原样的处理。5. 边界情况与隐藏坑长度不足 K、刚好整除、K1、null 链表这部分是面试官最喜欢深挖的地方也是你写代码时最容易被测试用例击穿的地方。我把常见的坑集中列一遍每个都附带原因和应对方式。5.1 链表长度不足 K 个时返回原链表这个最好理解。如果链表只有 4 个节点K5那任何一组都凑不齐结果就是原链表。在迭代版里第一轮判断就会 break。在递归版里base case 直接返回 head。很多人会漏掉这个判断导致在翻转 4 个节点时试图访问老五从而出现空指针异常。所以无论哪种解法第一步都是判断剩余长度是否足够。5.2 链表长度刚好是 K 的整数倍比如 1-2-3-4K2这种情况会翻转到底结果 2-1-4-3。这里没有不足 K 个的问题但要注意最后一组翻转后start 变成下一组的起点而这个起点是 null循环正常结束。有一种容易犯的错是在最后一组翻转后忘记把 pre.next 接到新头导致最后两个节点丢失。你只要记住无论翻转哪一组都必须执行 pre.next new_start 和 start.next next_group就能避免。5.3 K1 的情况K1 意味着一组一个节点翻转等于不变。如果代码里没有特判虽然也能跑通但会增加无意义的翻转操作。通常我会直接在最前面加一句if k 1: return head这样做一举两得既节省时间又能体现你考虑到了最小粒度的情况。面试官看到这行会觉得你思路非常缜密。5.4 空链表或 head 为 null这个是最基础的边界直接if not head: return None或者if head is None: return head。虽然简单但写上它表明你的代码健壮。很多候选人忘了写一旦测试用例传入空链表整个函数直接崩掉。虽然面试官一般不会因为空链表卡你但写好总归是加分项。5.5 翻转后原 head 不再是头节点这是链表题中必须时刻警惕的点。在 K2 的例子中原始 head1翻转后头变成 2。如果代码最终返回的是 head那结果就错了。迭代版通过 dummy.next 完美解决递归版通过返回 newHead 解决。记住一个原则永远不要想当然地认为 head 在函数结束后还是头节点。5.6 一个隐藏的陷阱翻转函数中 end 的判定我在前面代码里写的 reverse_between 循环条件是prev is not end。假如你写的是另一种常见写法def reverse_between(start, end): prev None curr start while curr ! None: next_tmp curr.next curr.next prev prev curr curr next_tmp return prev这个写法会把从 start 到链表末尾的所有节点全部翻转根本不管 end。所以如果你临时写一个通用的翻转一段函数必须把终止条件改为到 end 为止。否则在 K 个一组翻转中第一组翻转后你会发现后面所有组都被提前翻转了。这个坑我亲眼见过不少候选人踩过而且他们在调试时还会奇怪为什么结果链表乱成一团。6. 复杂度分析与进阶优化能不能从 O(n) 进一步压缩遍历次数先给出最简单的复杂度结论无论递归还是迭代时间复杂度都是 O(n)因为每个节点最多被访问两次一次数数一次翻转不过数数时也相当于访问常数系数不影响大 O。空间复杂度方面迭代法是 O(1)递归法是 O(n/K) 的递归栈空间严格说不是 O(1)。6.1 递归版的重复遍历问题递归版中每次调用 reverseKGroup 时都要去数当前剩余链表的 K 个节点然后在翻转阶段再次遍历这 K 个节点。也就是说每个节点可能被遍历两遍。虽然大 O 还是 O(n)但常数因子是 2。迭代版也有类似的现象判断阶段走一次翻转阶段走一次。实际上可以优化为只走一遍在判断长度时直接同时记录节点位置如果长度足够进入翻转阶段此时不需要再从头走。不过这种优化会稍微增加代码复杂度在面试中未必值得。我的建议是首先保证正确其次再谈优化。面试官问你有没有优化空间时你可以这样回答可以在一遍遍历中同时计数和翻转但编码时要更仔细目前这个版本已经满足线性复杂度并且在 K 很大时优势明显。6.2 K 值的影响K 越大需要翻转的组数越少翻转操作总次数仍然约为 n 次每个节点作为 curr 被处理一次。真正影响常数的是每次数 K 个节点时的指针移动。如果 K1数一次就结束如果 Kn只需要数 n 个节点然后翻转一整条链。最坏情况是 K2数数操作次数为 n翻转操作次数也为 n合计约 2n 次指针移动。这个常数在工程上完全可以接受。6.3 能不能用数组或栈来实现有些候选人会想到用数组存下所有节点然后分段翻转数组最后重新拼接。这确实能实现时间和空间复杂度都是 O(n)。但面试官通常不希望看到这种解法因为它避开了链表操作的考察点而且空间复杂度退化为 O(n)。你能想到用辅助空间说明你思维可以但如果你能直接用指针完成那才是面试官想要的答案。所以我不建议在面试中主动提数组解法除非面试官追问有没有其他思路。6.4 进阶变体题K 个一组翻转与链表重排这道题还有很多变体比如每隔 K 个节点翻转一组但不足 K 个时也要翻转又比如从链表尾部开始按 K 个一组翻转。理解核心思路后这些变体都是改几个条件而已。比如尾部开始翻转可以先反转整个链表再做从头翻转最后再反转回来或者先求长度再对齐起点。这些方法你不需要死记只要理解分解成子链表翻转组间连接这个模式就能举一反三。我个人最喜欢的一个变体是每 K 个节点翻转一组翻转后保留原顺序这没什么意义。另一个实用衍生是链表每 K 个节点逆序输出值但不改变链表结构这可以用递归回溯或栈来实现。这些题都能加深对链表操作的理解。7. 现场面试的实战步骤从拿到题目到写出 AC 代码的时间分配很多读者想知道面试现场应该怎么节奏。我根据自己的面试经验和指导学员的反馈总结一套行之有效的流程。7.1 第一步确认理解题意1-2 分钟拿到题目后先和面试官确认几个问题K 是正整数吗如果链表长度小于 K是保持原样吗K 是否可能为 1返回值要求是新的头节点吗这些确认不是废话它能让你避免掉进题目的文字陷阱同时给面试官留下审题严谨的印象。7.2 第二步举一个小例子手工模拟2-3 分钟不要急着写代码。先拿 K2、链表为 1-2-3-4-5 为例在纸上或白板上画出每一步指针变化。在模拟中你会发现翻转一组后必须用一个变量保存下一组的起点否则丢失链表。这也是我在面试中指导候选人时最强调的一步纸面推演能帮你省去 Debug 地狱。7.3 第三步说明思路与复杂度1-2 分钟用简明语言告诉面试官我将使用虚拟头节点用一个 pre 指针指向每组的前驱用一个 start 指针指向每组的第一个节点先判断剩余长度是否足够然后用三指针法翻转子链表最后接回。时间复杂度 O(n)空间复杂度 O(1)。说完后观察面试官反应如果他点头你再开始写。7.4 第四步编写代码5-8 分钟写代码时注意命名清晰不要用 a, b, c 这种无意义变量。用 dummy、pre、start、end、nextGroup 这类语义化命名。写完代码后不要马上说写完了先口头走一遍例子检查指针是否在每一步都正确。这比面试官指出错误要好得多。7.5 第五步针对边界情况口头测试2 分钟主动说我来检查几个边界情况——链表长度小于 K、K1、空链表。分别在代码中逐行推演确认返回正确。这个过程看起来有点多余但却是面试官评分的重要依据。你展示了自查能力即使代码有小 bug面试官也更愿意给你机会。我见过太多候选人能在二十分钟内给出 AC 代码但从不检查边界结果被测试用例一击即溃。反过来有些人代码写得很慢但每一步都自己验证面试评价反而更高。面试的本质是考察解决问题的能力而不是考察打字速度。8. 写这道题常见的四个错误模式以及对应的防治方法最后这部分我想集中讲讲我批改学生作业时遇到的各类 bug几乎每个人都会踩到至少一个。8.1 翻转函数用错了终止条件前面反复提到过如果你用标准的反转整个链表函数去翻转局部子链表它会把子链表后面的节点也卷进来。防治方法要么在翻转函数中传入 end 作为终止哨兵要么在翻转之前先断开 start 与后段的连接即让 end.next 指向 null翻转后再接回。两种方式都可以但我推荐传入 end 的方式因为不用额外断链代码更简洁。8.2 更新 pre 和 start 的顺序搞反在处理完一组后pre 应该更新为当前的 start因为 start 在翻转后变成了本组最后一个节点也就是下一组的前驱start 应该更新为 nextGroup。很多人会写反成 pre nextGroup、start start结果链表直接断掉或无限循环。记住在翻转前后start 对象的引用没有变只是它的 next 被改了。所以 pre start 是安全的start 仍然是那个节点对象。8.3 忘记在翻转前保存 nextGroup如果你先翻转 start 到 end再试图访问 end.next已经太晚了因为 end.next 已经被改成了前一个节点。所以必须在翻转前执行 nextGroup end.next把它存下来。这也是先记住下一组起点这条铁律的来源。8.4 没有把握 K1 的特殊性有些代码在 K1 时会陷入死循环因为翻转一个节点后pre 和 start 的更新逻辑可能导致 start 永远不为空。比如在迭代版中K1 时 end 始终等于 start翻转函数 reverse_between 返回 start 本身然后 nextGroup start.nextpre startstart start.next看起来没问题。但如果 reverse_between 的终止条件写错K1 时可能出问题。所以我坚持在函数开头特判 k1省心。如果你能把上面四个错误模式都避开这道题基本就稳了。更关键的是你在面试中展现出的调试思路和边界敏感性比背出任何标准答案都更能打动面试官。这道题目前已经进入各大公司算法题库的常青树位置不管投的岗位是后端、客户端还是算法面试官都喜欢用它来考察候选人的基本功。背下我的模板不难我真正希望的是你能理解每一步为何这样做。当你某天在面试中遇到K 个一组逆序重排之类的变体你就发现只要抓住虚拟头节点和局部翻转这两个工具什么花样都能拆解掉。