1. 理解题意的关键K个一组到底怎么分组先别急着写代码。算法题-25这一题LeetCode 第 25 题K 个一组翻转链表最坑的地方在于它看起来只是三行代码反转链表的进阶版实际上一上来就有五个指针在飞。我第一次做这题时连分组规则都理解错了以为和普通反转一样从哪开始翻就一路翻到尾结果最后一组不足 K 个也被翻了整个链表顺序直接乱套。1.1 原题复述与样例LeetCode 第 25 题的原题描述是给你一个链表每 K 个节点一组进行翻转请你返回翻转后的链表。K 是一个正整数它的值小于或等于链表的长度。如果节点总数不是 K 的整数倍那么请将最后剩余的节点保持原有顺序。注意不能只是改变节点内部的值而是需要实际进行节点交换。拿示例来说最直观。链表是 1 - 2 - 3 - 4 - 5K2那么分组是 [1,2]、[3,4]、[5]前两组内部翻转最后一组只有一个节点不足 K 个原样保留结果就是 2 - 1 - 4 - 3 - 5。如果 K3分组是 [1,2,3]、[4,5]第一组翻转第二组不足 3 个保留结果是 3 - 2 - 1 - 4 - 5。注意题目说的K 小于或等于链表的长度是常规情况实际上 K 完全可以大于链表长度此时整个链表不需要翻转。这也是一个常见的边界情况。1.2 三个隐藏边界第一个边界链表长度正好是 K 的整数倍。此时所有组都要翻转不会遇到最后不足 K 个的情况。很多人在这里出错是因为处理完一组后继续循环判断下一组时没有正确重置指针导致最后一段组头丢失。第二个边界链表长度不是 K 的整数倍最后剩下一段长度小于 K。这时候最后一段必须保持原顺序。这里的原则是先判断有没有满 K 个再动手翻转顺序不能反。如果你先翻再判断链表已经被破坏了。第三个边界K1 或者 K链表长度。K1 时每一组只有一个节点翻转等于没翻链表不变K链表长度时同样不变。这两个边界看起来简单但能把先检查再翻转的流程漏洞暴露出来。还有一个容易被忽视的点K0 不会出现在题目里但写通用工具函数时最好防御一下。1.3 分组与不足一组的处理分组操作本身不复杂从当前组头 head 出发用一个指针 cur 走 K 步如果能走到第 K 个节点就说明这一组是完整的如果 cur 为空说明剩余节点不足 K 个直接返回当前 head。这个提前走 K 步的判断是整道题的第一道安全门。举个例子链表长度为 5K2第一组从节点 1 出发走 2 步到节点 2cur 不为空可以翻。翻转后原来的组头变成节点 2组尾是节点 1。接下来从节点 3 出发走 2 步到节点 4继续翻。最后从节点 5 出发走 2 步第二步是空于是节点 5 保持原序。整个过程就是检查-翻转-移动-再检查。提示很多同学习惯在 while 循环里先翻转再判断下一组这是不对的。顺序必须是先判断本组是否满 K 个满则翻不满则停。2. 递归解法把大问题切成子问题2.1 递归思路递归解法的核心是把翻转整个链表这个大任务拆成翻转当前的 K 个节点 递归处理剩余链表。每次递归只处理一组剩余部分交给下一次递归。这个思路和归并排序的分治非常像先切一刀处理左边再处理右边最后把结果拼起来。不过这里的切不是从中间切而是从第 K 个节点后面切。我们要找到第 K1 个节点把它作为剩余子链表的头递归调用 reverseKGroup同时把当前 K 个节点翻转成一个新的子链表再把新子链表的尾节点指向递归结果完成拼接。之所以适合递归是因为链表天然有头节点的概念。每次切掉一段之后剩下的仍然是一个链表问题的结构没有变只是规模变小了。递归基自然就是剩余节点不足 K 个直接返回 head。2.2 代码实现我先把递归版本的完整代码贴出来语言用 Python方便阅读def reverse(head, k): prev None cur head while k: nxt cur.next cur.next prev prev cur cur nxt k - 1 return prev def reverseKGroup(head, k): cur head cnt 0 while cur and cnt k: cur cur.next cnt 1 if cnt k: return head new_head reverse(head, k) head.next reverseKGroup(cur, k) return new_head这段代码里最关键的是reverse(head, k)它只翻转以 head 开头的 K 个节点不关心后面的链表。翻转之后原来的 head 变成了这一段的尾节点所以head.next必须指向剩余部分递归处理后的结果。很多人会问reverse里 while k 循环为什么安全因为调用前已经确认当前组至少有 K 个节点cur 不会在中途变成空指针。如果没有前面的计数检查这里就会空指针异常。2.3 为什么递归空间复杂度是 O(n/k)递归的空间复杂度主要取决于递归调用栈的深度。每一层递归处理 K 个节点链表总长度是 n所以最多有 n/k 层递归。每层递归的局部变量占用常数空间总体空间复杂度是 O(n/k)。当 K 很小比如 K1 时递归深度是 n空间复杂度退化到 O(n)对于很长的链表就不太可行了。面试的时候我通常会把递归解法放在前面讲因为它逻辑清晰、容易说服人但讲完之后一定要补一句这个解法空间复杂度不是常数工程场景下我更倾向迭代。这样既展示了思路也展示了工程意识。另外Python 默认递归深度限制大约是 1000如果链表特别长而 K1直接会报 RecursionError。所以递归解法适合学习真正处理大数据量还得靠循环。3. 迭代解法用哨兵节点消除八成的指针焦虑3.1 哨兵节点设计迭代解法的难点在于链表的头节点可能被翻转比如 K2 时新的头是原来的第二个节点不再是原来的 head。如果直接对 head 操作返回时就不知道该返回谁了。解决这个问题最干净的办法是加一个哨兵节点 dummy让 dummy.next 始终指向当前链表真正的头。初始化时dummy ListNode(0)dummy.next head。然后我们维护一个 pre 指针它指向当前待翻转分组的前驱节点。pre 初始指向 dummy。这样第一组翻转之后直接把 dummy.next 更新为新的组头即可。3.2 核心思路迭代的每一轮循环做三件事第一寻找组尾让 tail pre然后 tail 向后走 K 步如果 tail 为空说明剩余节点不足 K 个直接退出第二翻转子链表记录 next_start tail.next把从 pre.next 到 tail 这段子链表从原链表中拆出来独立翻转第三接回原链表把翻转后的子链表头接到 pre.next把子链表尾接到 next_start然后更新 pre 为子链表尾继续处理下一组。这里的拆出来再装回去是最容易出错的地方核心是提前保存 next_start 指针。因为一旦在链表中做翻转如果没有保存下一组的起点后面的链表就丢了。3.3 完整实现与注释下面给出一版我实际跑过的完整实现逻辑清晰注释也写得比较细。先写一个辅助函数用来翻转从 head 到 tail 的闭区间子链表def reverse_range(head, tail): prev tail.next cur head while prev ! tail: nxt cur.next cur.next prev prev cur cur nxt return tail, head这里的while prev ! tail很关键prev 初始指向 tail.nextcur 指向 head。每次循环把 cur.next 改指向 prev然后两个指针同时前移直到 prev 走到 tail 位置。循环结束时整段子链表的指针方向全部反转并且尾部已经指向了 next_start。这种写法的好处是天然把子链表和外部链表断开不怕丢节点。然后是主函数class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def reverseKGroup(head, k): dummy ListNode(0) dummy.next head pre dummy while True: tail pre # 检查剩余节点是否够 K 个 for _ in range(k): tail tail.next if not tail: return dummy.next next_start tail.next new_head, new_tail reverse_range(pre.next, tail) pre.next new_head new_tail.next next_start pre new_tail这段代码里reverse_range返回两个值翻转后的子链表头和尾。接回去的时候pre.next指向 new_headnew_tail.next指向 next_start然后pre new_tail完成一组。我为什么推荐这个写法而不是在一段循环里做所有事因为封装之后主循环的意图非常清楚找组尾、翻转、接回。就算有人一个月后回来看这段代码也能一眼看懂。面试的时候干净的结构比花哨的炫技重要得多。4. 复杂度分析是面试的加分项4.1 时间复杂度先看外层每组翻转 K 个节点组数约 n/k。翻转 K 个节点的时间是 O(k)所以所有组的翻转时间加起来是 O(n)。再看找组尾每个 while 循环里tail 从 pre 出发走 K 步同样是 n 次步进。所以总时间复杂度是 O(n)。很多同学容易算成 O(n*k)其实不对。因为翻转 K 个节点和走 K 步找组尾都是按组进行的组与组之间没有重叠。每个节点最多被访问几次找组尾时访问一次翻转时访问一次接回时访问一次总共常数次。所以严格来说是 O(n)常数因子大约是 3。4.2 空间复杂度迭代解法只使用了 dummy、pre、tail、next_start 等常数个指针所以空间复杂度是 O(1)。这也是这道题最优的空间复杂度。递归解法因为调用栈深度为组数空间是 O(n/k)在极端情况 K1 时是 O(n)。所以如果你追求常数空间迭代是唯一选择。在面试里如果能主动说出递归空间 O(n/k)迭代可以压到 O(1)我下面用迭代实现会给面试官留下很好的印象。4.3 这道题和其他算法的联系链表题的魅力在于它经常和多类算法藕断丝连。比如归并排序的链表实现里需要找到链表的中点然后分治这道题的切组也和分治思想一脉相承都是把一个大链表切成互不重叠的子段分别处理再拼接。再比如贪心算法的每步局部最优这道题里每组的翻转都是独立的局部翻转不影响全局结构只不过拼接顺序需要刻意维护。理解了这些共通点遇到变体题时就不会慌。不过也要提醒一句别为了联系而联系。面试时讲这题可以用分治思想理解是加分的但硬扯 KMP 的 next 数组就很奇怪。KMP 是字符串单次匹配问题和链表分组翻转没有直接关系。5. 实测过程中最容易翻车的五个位置5.1 不足 K 个不翻转我第一版实现的错误很典型先翻转后判断。结果链表长度不是 K 的倍数时最后一组被强行翻转了。比如 1-2-3-4-5K2正确结果是 2-1-4-3-5我写成了 2-1-4-5-3因为最后 3 个节点被当成一组翻转了。原因就是我在翻转前没有完整地走 K 步检查。解决办法就是上面说的tail 走 K 步走不满直接 return。这里还有个细节for _ in range(k)里每走一步都要检查if not tail但初始 tail prepre 肯定不为空所以这个检查是从第一步之后开始的。如果链表刚好空了第二步就会触发返回。5.2 翻转后的头尾接错递归解法里head.next reverseKGroup(cur, k)这一行很多人会漏写。漏掉之后翻转后的子链表尾部没有指向下一段整个链表后半部分直接丢失。我当时查了很久才意识到原来reverse(head, k)只改变了组内节点的 next但组尾和下一段之间的连接需要手动设置。迭代解法里new_tail.next next_start也是同一类问题。我们的reverse_range内部会把 new_tail.next 指向 next_start但为了代码可读性主循环里再写一遍也没问题逻辑上是重复赋值但能强制自己意识到这里有个连接点。5.3 next 指针提前断裂迭代版翻转时我一度把nxt cur.next写在了更新cur.next之后导致下一跳地址丢失。正确的顺序永远是先保存后路再改方向。这个顺序在链表操作中几乎是铁律。如果你发现翻转后链表变成环或截断第一反应就是检查有没有提前覆盖 next 指针。在reverse_range里nxt cur.next必须在cur.next prev之前因为一旦改了当前节点的 next原来的 next 信息就丢了。5.4 哨兵节点的更新顺序迭代版里每处理完一组必须pre new_tail也就是把 pre 移动到当前组的尾部翻转后它成为下一组的前驱。我刚开始老把它写成pre new_head导致下一组从错误的位置开始检查链表结构直接被破坏。记住pre 永远是上一组的尾而不是本组的头。5.5 测试用例设计如果你只跑题目给的示例是发现不了这些问题的。我建议至少跑这组用例空链表head None任意 K返回 None。单节点链表。K1。K 等于链表长度整条链表完全反转。K 大于链表长度。链表长度正好是 K 的倍数。链表长度比 K 的倍数多 1也就是最后只剩一个节点。随机长度K2 和 K3。把这些用例写成测试一遍跑过之后基本可以放心提交。我在本地一直保持着暴力解法最优解法双写然后对拍的习惯对于链表题特别好用。6. 从一个题目到一类题目我的总结6.1 链表题通用练习路径如果你正在刷链表题我建议按这个顺序来先做 LeetCode 206 反转链表把单段反转写熟再做 24 题两两交换链表中的节点体会成组操作然后回到 25 题把 K 个一组翻转吃透最后可以做 148 排序链表、23 合并 K 个升序链表把链表操作和排序思想结合。这个顺序的好处是难度平缓206 是基础指针操作24 是两组25 是 K 组148 需要用到快慢指针拆链表和归并排序。等这些做完你再看链表的题目基本不会慌。6.2 变体题目K 个一组翻转链表的变体很多。比如只翻转奇数位置和偶数位置的节点、按段逆序输出但不修改链表、翻转链表中第 m 到第 n 个节点。这些题的核心都是同一件事找到边界、切断、翻转、再接回。只要你把 25 题的pre tail next_start这套模板记住变体题基本就是改边界条件。另外LeetCode 上还有一道反转链表 II要求在指定区间翻转它其实就是 K 个一组翻转的局部版本。建议大家把这几题归类整理形成一个链表翻转专题而不是一题一题孤立地刷。6.3 面试时怎么讲这道题面试遇到这道题一定不要上来就写代码。比较好的表达步骤是先复述题目确认 K 大于链表长度时怎么办、不足 K 个是否保持原序然后说明思路用 dummy 哨兵pre 指向当前组前驱tail 找组尾找到就翻转没找到就退出再分析复杂度时间 O(n)空间 O(1)。最后问面试官我可以用迭代实现吗得到肯定后再开始写。这比默写代码让人安心得多。我自己有一次就是因为先动手写写到半路发现 tail 判断写错了面试官看着很尴尬。后来改成先讲思路再写代码反而顺利过了。LeetCode 25 虽然只是众多算法题中的一道但它几乎是链表操作的试金石。如果你能把这道题的递归和迭代都写熟并且能解释清楚边界条件那你的链表基础基本就算过关了。至于后续要不要继续刷 KMP、归并排序、动态规划那些那就是另一个故事了。