先说个题号问题这题在 LeetCode 上是第 25 题Reverse Nodes in k-Group标题写成 105 大概率是笔误105 是另一道二叉树构造题。K 个一组翻转链表是 LeetCode 热门 100 题里的常客也是链表类题目里非常有代表性的一道——单看局部反转不难难的是把“数 k 个”“翻转一段”“接回原链”三个动作在循环里无缝串起来。很多刷题的人走到这题就卡住了单独写反转链表没问题一组合就写丢指针。这篇文章我按自己刷题时的完整思路拆开讲从最底层的指针设计到可运行的代码再到递归写法、边界条件、面试追问尽量把每一步为什么这么做说透适合正在刷题准备面试的读者也适合想把链表操作彻底吃透的同学。1. 先别急着写代码题目真正难在哪1.1 题面回顾与输入输出约定题目要求很简单给你一个链表头节点head和整数k从链表头部开始每 k 个节点一组对每组内部做反转最后再把所有组串回一条完整链表。如果最后一组节点数不足 k 个保持原顺序不动。几个典型例子输入链表1 - 2 - 3 - 4 - 5k 2输出2 - 1 - 4 - 3 - 5输入链表1 - 2 - 3 - 4 - 5k 3输出3 - 2 - 1 - 4 - 5输入链表1 - 2 - 3 - 4 - 5k 5输出5 - 4 - 3 - 2 - 1原题给的数据范围是节点数在[1, 5000]k的范围也是1到链表长度之间所以理论上不会有空链表输入但写代码时多防御一手也不是坏事。这里有一个所有链表题都绕不开的背景题目给的链表是不带头结点的单链表也就是第一个节点就是一个真实的数据节点。这种结构在做“可能改变头节点”的操作时特别容易出问题因为如果第一个节点被反转到了后面你返回时就不该返回原来的head而要返回新的头部节点。很多人在这一步就栽了后面我会专门讲怎么用哨兵节点解决。1.2 “分组翻转”背后其实是三个子问题的嵌套这题为什么比普通反转链表难一个量级因为普通反转链表只有一个动作从头到尾把指针方向掉个儿。而 K 个一组翻转是三个问题叠在一起子问题 A从当前位置向右数出 k 个节点确认这一组存在子问题 B把这 k 个节点的内部指针翻转子问题 C把翻转好的一组再接回链表剩余部分先给结论任何一个子问题单独拎出来都不难。面试挂掉的人通常不是不会翻转而是搞不定“这组翻转完了下一组的前驱到底是谁”。这个“前驱是谁”的问题恰恰是整个算法的核心。我打一个比方把链表想成一列火车车厢每组翻转就是把这 k 节车厢原地掉头。掉头之后原本在队尾的车厢变成队头原本在队头的车厢变成队尾。如果你只盯着掉头动作本身很容易忽略一件事——掉头之后火车头和后面车厢的连接点已经变了。你不能拿着旧图纸去接新火车。所以动手写代码前脑子里必须有一条清晰的时间线上一组处理完它的尾节点是谁当前组的起始节点是谁当前组翻转完成后新的头部是谁、新的尾部是谁。这四个位置只要有一个搞混代码跑起来必炸。2. 动手前的指针设计为什么必须制造一个哨兵节点2.1 不带头结点的单链表在翻转时有多难搞很多教材在讲链表时都会提到“带头结点”和“不带头结点”的区别。带头结点的链表第一个节点是个空壳不存数据专门用来统一空表和非空表的操作。可惜 LeetCode 的链表题基本都是不带头结点的考试做实验时如果遇到“不带头结点的单链表”的题目处理翻转时就会非常别扭。具体别扭在哪以翻转整条链表为例如果你老老实实地用三指针原地翻转翻转结束后原来的head已经变成了尾节点真正的头节点变成了原来的尾节点。你要么在翻转过程中把新头记下来要么在最后遍历到末尾再找一次。第一种办法需要多加一个变量第二种办法白白多了一次 O(n) 遍历。K 个一组翻转更麻烦第一组翻转前的“前驱”是null第二组翻转前的“前驱”是第一组的尾节点。这两个场景的处理逻辑不一样的话代码里就要写 if-else 分支。分支越多出错概率越高代码也越丑。解法就是人工造一个哨兵节点也叫 dummy 节点。它不存任何有效数据指向真正的头节点。有了它第一组的前驱就变成了 dummy和后面所有组的前驱完全统一。写循环的时候不再需要任何“是不是第一组”的特殊判断。提示这是一个非常重要的思维转变。很多链表题的难点不是不会写操作而是不想造 dummy。一个假节点换来逻辑的完全统一这笔买卖非常划算。2.2 四个关键位置的明确分工写出代码之前先在纸上把下面四个变量画出来之后所有操作都围绕它们展开变量初始位置翻转完成后的位置作用dummy链表头部之前固定不变提供统一前驱返回新头predummy当前组的尾部每一组的前驱节点startpre 的下一个节点当前组的尾部当前组的第一个原始节点curpre当前组的第 k 个节点用来检测分组是否完整这里最关键的变量是pre。它始终指向“当前组之前的那一个节点”也就是当前组翻转后的新头将要接上去的位置。第一轮pre是 dummy第二轮pre是第一组的新的尾节点也就是原来的第一个节点。start和cur的关系也要搞清楚翻转前start是组内第一个cur是组内第 k 个翻转后cur变成组内新的头start变成组内新的尾。下一轮开始时pre就要移动到start这个位置因为它现在是整条链表中“当前组尾巴”的所在处。我见过不少初学者在翻转后还傻傻地让pre pre.next这就不对了。pre.next在翻转过程中被改成了新头而下一组的前驱应该是旧头变成的新尾也就是start。这个点一句话总结翻转的终点就是下一轮翻转的起点。3. 迭代解法数节点与头插翻转的完整过程3.1 可直接运行的 Python 代码先给出我比较喜欢的迭代写法用的是“数节点 头插法”的思路。整段代码不长核心就两个循环第一个循环数 k 个节点第二个循环做 k-1 次头插。class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def reverseKGroup(head: ListNode, k: int) - ListNode: dummy ListNode(0, head) pre dummy while True: # 第一件事从 pre 出发数 k 个节点 cur pre for _ in range(k): cur cur.next if cur is None: return dummy.next # 此时 cur 指向当前组的第 k 个节点start 是组内第一个节点 start pre.next # 第二件事用头插法翻转 [start, cur] 这一段 # 只循环 k-1 次把 start 后面的 k-1 个节点依次挪到 pre 后面 for _ in range(k - 1): tmp start.next start.next tmp.next tmp.next pre.next pre.next tmp # 翻转完成后start 变成了本组的尾节点 # 下一组的前驱就是 start pre start简单解释一下这个代码的结构外层的while True不停地处理每一组每处理完一组就把pre推进到本组的末尾继续处理下一组。什么时候结束在数节点的过程中发现不够 k 个节点直接返回dummy.next。这个返回值是整个算法最终的新链表头。3.2 用具体实例推演一遍链表变化光看代码可能还是转不过来我们拿1 - 2 - 3 - 4 - 5k 2完整地走一遍。初始状态dummy - 1 - 2 - 3 - 4 - 5 pre 指向 dummy第一轮循环cur pre然后走 2 步cur先到 1再到 2。2 非空说明第一组存在。start pre.next 1注意这里start指向的是节点 1不是它的值后面我们一直用这个节点作为翻转的“锚点”。头插翻转只做k-1 1次tmp start.next也就是节点 2start.next tmp.next节点 2 的下一个是 3所以 1 现在指向 3tmp.next pre.next节点 2 的 next 指向 1pre.next tmpdummy 的 next 指向 2一轮操作后链表变成dummy - 2 - 1 - 3 - 4 - 5此时pre start 1注意 1 现在已经是这一组的尾部。第二轮循环cur pre 1走 2 步先到 3再到 4。非空第二组存在。start pre.next 3。头插翻转 1 次tmp 43.next 54.next 31.next 4因为此时pre指向 1pre.next原本是 3改成 4链表变成dummy - 2 - 1 - 4 - 3 - 5pre start 3。第三轮循环cur 3走 2 步先到 5再到 None。cur is None说明剩下的节点不足 k 个直接return dummy.next。最终输出2 - 1 - 4 - 3 - 5符合预期。再试一下k 3的情况前两轮我不写那么细只列关键变化第一组1 2 3翻转后链表变成dummy - 3 - 2 - 1 - 4 - 5第二组只剩4 5不足 3 个直接返回结果3 - 2 - 1 - 4 - 5也完全正确。3.3 头插法为什么只循环 k-1 次这是初学者最容易困惑的地方明明要翻转 k 个节点为什么头插只做 k-1 次想明白这个问题关键在于理解头插法的动作含义。start指针在整个过程中始终指向当前组的第一个原始节点它永远不会移动。每次循环做的事情是取出start.next指向的那个节点把它摘下来插到pre的后面。举例pre - start - a - b - c这一段有 4 个节点目标是翻成c - b - a - start。第一次把 a 摘到 pre 后面变成pre - a - start - b - c第二次把 b 摘到 pre 后面变成pre - b - a - start - c第三次把 c 摘到 pre 后面变成pre - c - b - a - start看到了吗start一直在原地它后面的节点被一个接一个搬到最前面。搬完 k-1 个节点之后自然就完成了 k 个节点的逆序。因为第一个节点start不需要搬自己它只需要原地等着最后自动变成新尾部。这个技巧在其他链表题里也很有用。比如“把某段链表反转”的变体题用头插法能少维护一组指针只需要知道区间头的前驱和区间末尾的后继就行。4. 边界条件与高频错误这些问题我替你先踩了一遍4.1 “不足 k 个保持原序”的检测时机LeetCode 25 有一个非常明确的硬性要求最后一组不足 k 个节点时保持原始顺序不做翻转。检测这个条件的时机必须在动手翻转之前不能在翻转过程中发现不够了再回头补救。检测方式常见的有两种我对比一下# 写法一判断 cur 是否为 None推荐 cur pre for _ in range(k): cur cur.next if cur is None: return dummy.next# 写法二判断 cur.next 是否为 None cur pre for _ in range(k): if cur is None or cur.next is None: return dummy.next cur cur.next两种都能用但写法二有个隐患如果cur本身已经是 None访问cur.next会直接报空指针异常所以必须先判断cur is None。写法一每次都在移动之后再判断天然避免了这个问题。还有一个细节值得注意这里的cur是从pre出发的不是从start出发的。为什么要从pre出发因为pre是当前组的前驱它本身不是当前组的成员。从它出发走 k 步正好定位到第 k 个节点如果是从start出发走 k 步会走到第 k1 个节点也就是下一组的头语义就不一样了。4.2 三个高频手误代码片段第一类错误是头插四行的顺序写反。很多人会写成tmp start.next tmp.next pre.next start.next tmp.next # 错误此时 tmp.next 已经变成旧的 pre.next pre.next tmp第三行start.next应该取的是tmp.next但tmp.next在第二行已经被改掉了。链表的特点就是你一旦改了某个节点的 next原来它指向谁就再也找不回来了。正确的顺序必须是先把旧连接记录到start.next取出并摘掉再改tmp.next插入新位置。用一句话记先摘后接顺序不能乱。第二类错误是翻转之后忘了让pre start。我前面特意强调过翻转完成后start已经是本组的尾部下一轮所有操作都要以它为前驱开始。如果这里写成pre pre.next那pre就指向了本组翻转后的新头等于跳过了本组的尾巴下一组分组的起点直接错乱。代码往往不会立刻报错而是输出一个完全莫名其妙的结果让人排查半天。第三类错误是最后返回了head而不是dummy.next。第一组翻转后真正的链表头已经变了。比如1 - 2 - 3 - 4k2翻转后是2 - 1 - 4 - 3新的头是 2。如果你还返回原来的head也就是 1输出的就是1 - 4 - 3凭空丢了节点 2。4.3 特殊输入k1、k 等于链表长度、单节点链表先看k 1的情况。按题目定义每一组只有一个节点“翻转一个节点”等于没翻转所以整个链表保持原样。对照代码内层头插循环执行k-1 0次什么都不做pre start之后继续跑下一轮直到检测到数不到节点返回。这个过程完全走得通不需要单独写 if。再看k等于链表长度的情况。整条链表被分成一组做完一次完整反转后pre会走到原来的第一个节点此时pre.next是 None下一轮数节点时第一步就发现cur is None直接返回。返回的就是完全颠倒的链表结果正确。链表只有一个节点的情况也顺一遍pre指向 dummy数 k 个节点——这里假设 k 至少为 1——第一步cur cur.next就到这个唯一节点如果 k 更大第二步cur变 None返回原链表。如果 k 正好等于 1翻转 0 次返回原链表。同样安全。提示写链表题的通用习惯——在提交前把k1、kn、两个节点、一个节点这些极端输入在心里各跑一遍。不要嫌麻烦链表题的 bug 九成出在边界上。5. 递归写法把区间翻转交给函数边界5.1 走 k 步定位区间边界翻转半开区间迭代法需要维护dummy和pre思路直接但指针多。递归写法能把逻辑拆得更干净递归函数只负责“翻转当前这一组然后递归处理下一组”。下面是我常用的递归实现def reverseKGroup(head: ListNode, k: int) - ListNode: # 先数 k 个节点如果不够 k 个直接返回 head保持原序 cur head for _ in range(k): if cur is None: return head cur cur.next # 此时 cur 指向第 k1 个节点也就是下一组的起点 # 翻转从 head 到 cur 之前这一区间的节点 prev None node head while node ! cur: temp node.next node.next prev prev node node temp # 翻转完成后 # prev 是当前组的新头原第 k 个节点 # head 是当前组的新尾原第一个节点 head.next reverseKGroup(cur, k) return prev这个版本的代码量比迭代版还少。递归终止条件藏在了第一步“数 k 个节点”里一旦发现不够 k 个直接返回当前head等于告诉上层不用翻转了。5.2 为什么递归版里的边界是 cur 而不是第 k 个节点这里有个很容易绕晕的差异递归版第一步让cur走了 k 步走出来之后cur指向的是第 k1 个节点而不是第 k 个节点。迭代版里cur走 k 步指向的是第 k 个节点。这是两套不同的区间定义。迭代版操作的是闭区间[start, cur]两头都是组内节点。递归版操作的是半开区间[head, cur)包含head不包含cur。循环终止条件是node ! cur也就是说只要node还没走到区间右边的边界就继续翻转。半开区间的好处是递归调用直接传cur就能处理下一组因为cur天然就是下一组的头。这种“边界节点不参与本组操作”的写法在链表递归题里很常见能少写很多“保存后继节点”的代码。验证一下例子1 - 2 - 3 - 4 - 5k 2。第一次调用数 2 步cur指向 3。翻转[1, 3)这段区间结果是2 - 1。然后head也就是 1的next指向reverseKGroup(3, 2)的结果。第二次调用head是 3数 2 步cur指向 5。翻转[3, 5)结果是4 - 3。然后 3 的next指向reverseKGroup(5, 2)。第三次调用head是 5数 2 步第一次cur到 None不满足条件返回 5。一层层返回之后整体就是2 - 1 - 4 - 3 - 5完全正确。5.3 迭代和递归的取舍把两种写法放在一起对比维度迭代头插法递归半开区间法时间复杂度O(n)O(n)额外空间O(1)O(n/k)递归栈深度代码长度稍长更短边界理解成本指针多易混淆区间概念更抽象一点面试推荐程度最推荐空间最优加分项展示思路多样性我的建议是面试时优先写迭代法因为空间复杂度 O(1) 是一个很干净的加分点而且面试官追问边界情况时迭代法的四个指针比递归的区间边界更容易讲明白。递归写法可以作为“另一种思路”提出来如果面试官眼睛一亮让你实现再写递归不迟。不过站在刷题训练的角度递归版本一定要自己手写一遍。它能帮你建立“把链表切片给子问题”的直觉这种直觉在解决更复杂的链表题时非常有用。6. 从这题延伸出去面试追问和变体6.1 面试官常问的变体K 个一组翻转链表这道题面试官很少只让你写完就结束常见追问我整理一下。第一个变体如果最后一组不足 k 个也要翻转怎么办改动的代价很小删除“数 k 个节点时发现不足就返回”的判断逻辑即可。但要注意不能直接删掉数节点的循环因为你仍然需要找出每一组的第 k 个节点或者下一组起点只是不再在不够的时候提前退出。第二个变体k 2时这题变成“两两交换链表中的节点”对应 LeetCode 24。理解了 K 个一组翻转后24 就是它的一种特例。用迭代解法去解 24代码可以简化为每轮只做一次头插。第三个变体链表节点值都相同只靠节点身份区分对解法有影响吗没有。我们的所有操作都只修改指针不比较值所以节点值是否相同完全无影响。这也是链表题和数组题的一个重要区别数组交换的是值链表交换的是指向关系。第四个变体如果 k 不是固定值而是一个数组要求分别按不同步长翻转那就要重新设计分组策略相当于每个区间单独调用一次局部翻转复杂度会上升。这种属于强力追问能想清楚就说明你对指针的掌控已经到位。6.2 复杂度分析和一个刷题建议两种写法的时间复杂度都是 O(n)每个节点被访问的常数次——数节点时经过一次头插或递归翻转时又经过一次整体线性完成。迭代版额外空间 O(1)递归版因为要按组调用递归深度约等于 n/k空间复杂度 O(n/k)。这道题好在哪它不是一道孤立的知识点题而是把“局部反转链表”“链表区间划分”“边界连接”三个考点放在一起的综合题。做一遍能明显感觉到自己对链表的掌控力会上一个台阶。以我个人的刷题经验这种题值得三刷。第一遍看题解照抄把代码跑通理解每一步在干什么第二遍合上题解照着思维过程自己推演能独立写出来算过第三遍限制自己在 15 分钟内写出 bug-free 的版本再去刷几道变体巩固。链表题的核心其实就一句话每次动 next 之前先问自己这个节点是唯一还在指向它的入口吗动完之后还能不能找回这条链。只要时时带着这个问题写代码绝大多数链表题都能稳拿下来。