K个一组翻转链表：递归与迭代双解法详解

1. 题目拆解：先说清楚这题到底在考什么

1.1 从题目描述看真实意图

力扣hot100第31题“K个一组翻转链表”，题面看起来很短：给你一个链表，每K个节点一组进行翻转，不足K个保持原样，最后返回翻转后的链表。

但你要是真把这题当成“每隔K个翻一次”来做，大概率会栽。我见过不少刷题群里的朋友，第一次写这题时都把它等同于“单链表逆序”，结果写完才发现翻完一组之后，跟上一组和下一组的连接全是坑。

它真正考的东西，在我看来是三件事：

• 链表的指针操作熟练度。这题不像数组题可以随意索引，每一步都得靠指针“穿针引线”，一个指向错了就断链。
• 递归思维或者迭代拆解能力。这题用递归来写非常优雅，但你得能想明白“把前K个翻转之后，剩余部分天然是一个更小规模的同一个问题”。
• 对边界条件的敏感度。剩余节点数不足K时保持原样，这个条件看起来简单，实际写起来很容易判断错。

这题在hot100里的编号是31，难度标的是困难，但说实话，它属于“困难题里比较友好的那一档”。它不像动态规划那样需要你凭空想出状态转移方程，也不太考数学推导，只要你链表基本功扎实、递归写得熟，就是一个可以稳定拿下的题目。

1.2 为什么这道题能进hot100

刷过力扣hot100的人应该都有个感觉：这100道题不是随便挑的困难题，而是按“算法思维覆盖度”来选的。K个一组翻转链表这道题能入选，是因为它一个题目同时覆盖了链表操作里最高频的两类思维模型：局部翻转 + 递归分解。

而且它在实际面试中出现频率也不低。很多公司面试官喜欢拿它当“中等偏上难度”的题目来考，又能考察代码风格，又能追问各种变体。你把这题吃透了，等于同时掌握了链表的头插法、尾插法、递归思想、迭代指针操作，一举多得。

我自己刷这题的时候，第一遍用的是迭代，第二遍用递归重写，后来又用这题的思路去解了几道类似的链表题，感觉收获远大于题目本身。下面把这两条路都走一遍，你按照自己的偏好选一条主攻就行，但建议两条都写一遍。

2. 解题思路选型：递归和迭代，两条路怎么选

2.1 递归解法：“先翻一组，剩下的交给函数”

递归的思路是：我先把链表前K个节点翻转，翻转完之后，原来的第K个节点变成了这一段的新头，原来的头节点变成了这一段的新尾。此时新尾的next应该指向谁？应该指向“剩余链表以同样规则翻转后的结果”。

这个“剩余链表以同样规则翻转后的结果”就是递归调用本身。你不需要手动去迭代处理后面所有的组，只需要把子问题定义清楚：reverseKGroup(head, k)表示“以head为头节点的链表，按K个一组翻转后返回新头”。

基于这个定义，递归的逻辑就是：

1. 先检查从head开始是否还有K个节点。如果不够K个，直接返回head。
2. 如果够K个，就翻转这K个节点。
3. 翻转完后，原来的head变成了这K个节点的尾部，此时让head.next指向reverseKGroup(下一组的头, k)。
4. 返回这K个节点的新头。

很多初学者会卡在第3步，搞不清楚“下一组的头”到底是谁。这里关键在于：翻转前，你要先走到第K个节点，把它的next存下来作为nextGroup；翻转中，prev会从head一路走到第K个节点。翻转完成后，prev就是新头，head就是新尾，而nextGroup就是下一组的开始。

递归函数要不要返回值？要，返回值就是翻转后这一段的新头。

这个思路的妙处在于：每一层递归只处理K个节点，剩下的部分完全交给下一层，逻辑极度清晰。你不需要维护一堆prev、next指针来跨组连接，因为跨组连接天然由递归的返回值完成。

2.2 迭代解法：三指针原地翻转

递归虽然优雅，但有些面试官会追问“你能不用递归写吗”，或者你会担心递归栈溢出。这时就需要迭代解法。

迭代解法的整体框架是：先遍历链表计算长度，算出总共需要翻转多少组，然后用一个循环，一组一组地翻转，每一组翻转后要把组头和组尾跟前后组正确连接。

单组翻转怎么做？其实就是单链表逆序的三指针法：

• pre指向当前组的前一个节点（也就是上一组的最后一个节点）
• cur指向当前组的第一个节点
• 在组内用一个循环，把每个节点的next指向前一个节点

但这里有个关键区别：如果只是简单地把组内节点逆序，你会发现组头和上一组的连接、组尾和下一组的连接都需要额外维护。所以迭代写法通常要用到四个指针：pre（上一组尾部）、start（当前组头部）、end（当前组尾部）、nextGroup（下一组头部）。

翻转完之后：

• pre.next要指向翻转后的新头（也就是原来的end）
• start.next要指向nextGroup

然后移动pre到start（注意，此时start已经是翻转后的尾部），移动cur到nextGroup，继续下一组。

这个写法信息量比较大，光看文字很难一次理清，我建议你动手画个图。画图方法我后面会讲。

2.3 递归 vs 迭代：时间、空间、可读性对比

时间复杂度两者一样，都是O(n)。因为不管哪种写法，你都得把每个节点至少走一遍。空间上迭代明显占优，但递归也远不算差，毕竟递归深度是组数而不是节点数，对于K个一组翻转来说，即使有十万个节点、K=2，递归深度也只有五万层，在大多数情况下都够用。

我的建议是：以递归为主解法，因为代码短、逻辑清晰、不容易写错，面试时讲思路也更好讲。但迭代你至少要看懂，因为有的面试官会明确要求写非递归版本。下面两种写法都给你完整代码。

3. 手把手实现：两种写法的完整代码与边界处理

3.1 递归写法：C++ 和 Python 双版本

先用C++写一版。C++写链表题需要特别注意指针的语义，别把指针指向搞混了。

class Solution { public: ListNode* reverseKGroup(ListNode* head, int k) { if (head == nullptr) return nullptr; // 先检查剩余节点是否够 k 个 ListNode* tail = head; for (int i = 0; i < k; i++) { if (tail == nullptr) { return head; // 不足 k 个，保持原样 } tail = tail->next; } // 此时 tail 指向第 k+1 个节点，也就是下一组的头 // 翻转前 k 个节点，标准三指针法 ListNode* pre = nullptr; ListNode* cur = head; while (cur != tail) { ListNode* nxt = cur->next; cur->next = pre; pre = cur; cur = nxt; } // 翻转完成后： // pre 指向翻转后的新头 // cur 指向 tail，即下一组开头 // head 变成翻转后的尾部 head->next = reverseKGroup(tail, k); return pre; } };

这版代码有个特别容易让人困惑的地方：while (cur != tail)这个循环条件。注意tail已经提前走到了第k+1个节点，所以循环只需要翻到第k个节点就停，不会多翻。这也是为什么先检查“够不够k个”如此重要——检查的过程顺便拿到了下一组的头，一箭双雕。

再看Python版本，Python写链表题指针语义和C++类似，但语法更简洁：

class Solution: def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]: # 检查剩余节点是否够 k 个 tail = head for _ in range(k): if tail is None: return head tail = tail.next # 翻转前 k 个节点 pre = None cur = head while cur != tail: nxt = cur.next cur.next = pre pre = cur cur = nxt # 递归处理剩余部分 head.next = self.reverseKGroup(tail, k) return pre

两个版本的逻辑完全一样。你如果会C++就仔细看C++那版，会Python就看Python版，核心就一个：检查够不够k个，够了就翻，然后递归处理剩下的。

注意：递归写法里head->next = reverseKGroup(tail, k)这一行顺序不能写反。一定要先翻转，再递归，再连接。如果你先递归再翻转，递归返回后的链表状态会跟你预期的不一致，很容易绕晕。

3.2 迭代写法：四个指针的完整推导

迭代写法我同样用C++来写，因为指针逻辑用C++表述最清晰。核心思路是：先把链表长度算出来，算出一共有多少组需要翻，然后一组一组翻。

class Solution { public: ListNode* reverseKGroup(ListNode* head, int k) { // 第一步：计算链表长度 int length = 0; ListNode* node = head; while (node != nullptr) { length++; node = node->next; } // 建立虚拟头节点，统一处理头节点被翻转的情况 ListNode* dummy = new ListNode(0); dummy->next = head; ListNode* pre = dummy; // 上一组的尾部 ListNode* cur = head; // 当前组的头部 while (length >= k) { // 找到当前组的尾部 end ListNode* end = cur; for (int i = 1; i < k && end != nullptr; i++) { end = end->next; } if (end == nullptr) break; // 保存下一组的头 ListNode* nextGroup = end->next; // 翻转当前组的 k 个节点 ListNode* prev = nullptr; ListNode* curr = cur; while (curr != nextGroup) { ListNode* nxt = curr->next; curr->next = prev; prev = curr; curr = nxt; } // 翻转完成后： // prev 指向翻转后的新头（原来的 end） // curr 指向 nextGroup // 连接：上一组的尾部指向翻转后的新头 pre->next = prev; // 当前组翻转后的尾部（原来的 cur）指向下一组的头 cur->next = nextGroup; // 移动 pre 和 cur，进入下一组 pre = cur; cur = nextGroup; length -= k; } return dummy->next; } };

迭代写法的核心在于，组内翻转完成后，pre->next = prev连上前半部分，cur->next = nextGroup连上后半部分。这两个连接缺一不可。我在第一次写迭代版时，就是忘了cur->next = nextGroup这一行，导致整个链表后半段全丢了，debug了半天。

最后pre = cur这一步，是很多人的困惑点。这里要特别注意：此时cur还是原来的组头，但这个节点经翻转后已经是整组节点的尾部了。所以pre更新为cur，实际上是让pre指向这一组的尾部，也就是下一组的前驱节点。这一步千万别写成pre = prev，否则下一组翻转完连接时就会出错。

3.3 虚拟头节点：为什么必须用它

迭代写法里我引入了一个dummy虚拟头节点，这一步绝对不是可有可无的。

原因很简单：如果整个链表长度大于等于K，那么第一次翻转之后，链表的头节点会变。比如链表是1->2->3->4->5，K=2，翻转第一组后变成2->1->3->4->5，头从1变成了2。如果你没有虚拟头节点，每次翻转完都得特判“如果这是第一组，就更新返回的头节点”，代码会变得支离破碎。

有了虚拟头节点之后，不管哪一组翻转，它的前驱节点都存在，不需要做任何特殊判断，最后统一返回dummy->next就行。这个技巧不仅在这题有用，几乎所有涉及“头节点可能会变”的链表题，都应该想到用它。

递归写法不需要虚拟头节点，因为递归每一层只管自己这一段，新头直接由返回值搞定，不需要额外的统一入口。这也是递归写法的优势之一。

4. 常见错误与调试技巧实录

4.1 你一定会犯的错：指针更新顺序搞反

我把刷题群里出现频率最高的报错场景列一列，你看看有没有你自己的影子：

• for循环里的tail = tail->next没有提前判空。这种情况在测试用例里有不足K个节点的链表时会直接空指针异常。
• 翻转循环里把nxt = cur->next这一行漏了，或者写在了cur->next = pre之后。一旦先改了cur->next，原来的cur->next就找不回来了，链表直接断掉。
• 迭代翻转完成后，忘记让cur指向nextGroup，导致下一次循环时还在原地打转。

我自己的经验是：链表题的指针操作，不要靠脑子想，一定拿纸笔画。每一轮循环开始前，把三个指针（pre、cur、nxt）指向哪个节点画出来；循环结束后，再画一遍。能画出两张图，代码就不会错。

注意：组内翻转的循环条件while (cur != tail)和while (curr != nextGroup)是等价的，区别只是提前把tail/nextGroup存下来了。如果你写的是while (cur != tail)，那tail必须是在翻转前就确定好的；如果写的是while (curr != nextGroup)，那nextGroup同样得提前保存。这两个值都不能在翻转过程中临时去找，因为翻转会破坏原来的next关系。

4.2 递归写法最容易让人懵的两个点

第一个点是reverseKGroup(tail, k)返回的到底是什么。注意tail是第k+1个节点，也就是下一组的头。这个递归调用会处理“从tail开始、以同样规则翻转”的链表，并返回处理后的新头。所以head->next = reverseKGroup(tail, k)的意思就是：让当前组翻转后的尾部接上后续处理完的结果。

第二个点是：为什么翻转完第一组后，head就是新尾？因为翻转前head是这一组的第一个节点，翻转后它变成了最后一个节点。这个节点的next原本指向第二个节点，但翻转过程中它已经被改成指向pre（初始是nullptr），所以翻转完后要专门给它设置next。如果不设置，这个节点就成了链表终点，后面的组全丢了。

这两个点想通了，递归版基本就没障碍了。我见过不少人递归版代码写对了，但问他“head->next为什么要这样接”，答不上来。面试时如果答不上来，考官还是会认为你没掌握。

4.3 测试用例设计：怎么验证你的代码是对的

刷题最忌讳的就是代码一跑过样例就提交，结果WA（Wrong Answer）了才开始慌。我建议你每写完一道链表题，固定用下面这组测试用例来验证：

最后一个用例很关键。K=1时，代码里的翻转循环会直接跳过，链表保持不变。如果你没考虑K=1，有些写法会陷入死循环或者出现空指针。

还有一个很多人会忽略的细节：当K非常大（比如K=1000000）而链表只有几个节点时，你的代码不能崩。递归写法里那个“检查够不够K个”的循环要能快速返回，迭代写法里初始化长度也是O(n)，都没问题。但如果你在翻转循环里用了for (int i = 0; i < k; i++)又没判空，就会直接空指针。

5. 面试追问与扩展思考

5.1 面试官常问的“变体”怎么答

这道题在面试中经常被扩展成几种变体，提前想一想会有很大优势。

第一种：不足K个也要翻转。逻辑变化是最小的，你只需要把递归版本里第一段“检查够不够K个”的提前返回去掉，并在翻转循环里加上cur != nullptr的判断。迭代版本里，把while (length >= k)改成do...while或者干脆不用长度判断，直接翻到底。

第二种：让你用“交换相邻节点”的方法，而不是K个一组翻转。这对应的是力扣另一道题“两两交换链表中的节点”，本质上就是K=2的特例。你如果这题的递归写法写熟了，那道题就是一行递归的事。

第三种：要求你返回每一组翻转后的中间状态，也就是不只返回最终结果，还要能打印每一轮翻转后的链表。这种问题考察的是你对翻转过程中中间状态的理解，画图熟练的话这也难不倒你。

第四种：只翻转链表中第a到b个节点。这个思路跟本题一模一样，只是你先把指针走到第a-1个节点，然后以它为“pre”，翻转K个改成翻转(b-a+1)个。你会发现，K个一组翻转这个写法，本质上是把这个局部翻转操作重复执行了多组。

5.2 从一道题到一类题：递归模型的迁移

K个一组翻转链表背后其实是一个非常通用的递归模型，我给它起了个名字叫“分组处理模型”：拿到链表头部，先处理前一小段，后一小段交给递归。

在力扣hot100里，你可以用这个思路去解好几道题：

• 合并两个有序链表：比较头部大小，小的节点指向剩余两个链表的递归合并结果。
• 反转链表：递归版就是先翻后面所有，再把当前节点接到尾部后面。
• 两两交换链表中的节点：K=2的分组翻转，思路一模一样。
• 有序链表转换二叉搜索树：找到中点的前驱，断开链表，左右两部分递归建树。

所以你可以把这道题当作一个模板题来刷。把这题的递归逻辑吃透了，上面那几道题你至少有一半能秒解。

另外说一句，链表题里那种“画图、定义进出、写循环、跑例子”的节奏，是通用的。无论你是刷力扣还是面试，这套方法都适用。我在刷题群带过几个朋友，每次他们链表题卡住，我就说一句话：“画图，把每个指针的指向标出来。”这一步做到了，80%的错误都能自己发现。

6. 最后再做一个小分享

我自己刷这题的经历比较特别：第一次是在某厂面试前夜临时抱佛脚看的递归解法，当时看懂了但完全没消化，第二天面试官让我手写，我画了五分钟图，写了一版迭代，最后过了。后来在刷hot100时又刷到这一题，才真正把递归和迭代都吃透。

所以我的体会是：不要怕一开始看不懂，也不要在没画透指针关系的情况下硬写代码。这题就是典型的“画图两分钟，代码两分钟”的题目，如果你十分钟没写出来，大概率不是你不懂算法，而是你没把图理清。先把草稿纸拿出来，画三张图——翻转前、翻转中、翻转后——再落笔。

还有一个很实用的小技巧：刷题的时候，把每道链表题的测试用例都固定带几组，比如“空链表、单个节点、全部翻转、部分翻转”这四类。以后不管遇到哪道链表题，直接套这套用例，能省掉大量调试时间。我自己现在刷题已经养成了这个习惯，效率提升非常明显。

这题之后，建议你紧接着把“两两交换链表中的节点”和“反转链表II”一起刷了。三题放在一起对比，你对链表递归和迭代的理解会直接上一个台阶。