K个一组翻转链表——分组递归与迭代的完整实现
K个一组翻转链表——分组递归与迭代的完整实现
适读人群：有链表反转基础的 Java 工程师 | 阅读时长：约22分钟 | 难度：Hard
开篇故事
25 题是我刷 LeetCode 时真正卡过的题目之一。不是算法思路想不到，而是工程实现上各种边界对不上，指针一复杂就乱。
那是我刷题第一年，把 206（反转链表）和 92（区间反转）都做得比较熟了，一看 25 题以为轻车熟路——不就是每 K 个为一组重复 92 题的操作吗？结果实际写代码时，"如何判断剩余节点数够不够 K 个""如何把每组反转后的结果拼接起来"这两个问题搞了我很久。提交了四五次才过，每次挂的都是不同的边界用例，改一个又引出另一个问题。
真正搞懂这道题之后，我意识到它其实是链表题里一道综合性极强的题目。递归版本优雅但空间 O(n)，迭代版本代码量大但空间 O(1)，各有侧重。这篇文章把两种实现都写完整，每行代码都解释清楚，不留死角。
一、题目解析
题目：LeetCode 25. K 个一组翻转链表
给你链表的头节点 head，每 k 个节点一组进行翻转，请你返回修改后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
示例：
输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]
输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]约束条件：
- 链表中的节点数目为 n
1 <= k <= n <= 50000 <= Node.val <= 1000
进阶要求：你能不能只使用常数额外空间来解决此题？（即空间 O(1) 的迭代版本）
考点梳理：
- 如何计数每组 K 个节点，不足 K 个时保持原顺序
- 单组反转后如何正确接入下一组
- 整体结构的递归分解或迭代控制
- 哑节点的运用
- 进阶：O(1) 空间的纯迭代实现
二、解法一：暴力解法——按组收集再重建
思路
遍历链表，按组收集节点。每收集满 K 个节点，就把这组节点翻转（用栈或者就地翻转），然后拼接到结果链表上。最后不足 K 个节点的直接附加到末尾。
实现上用栈最直观：把 K 个节点压栈，然后依次出栈，出栈顺序就是翻转后的顺序。
完整代码
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy; // 结果链表的尾节点
ListNode curr = head;
while (curr != null) {
// 收集最多 k 个节点
Deque<ListNode> stack = new ArrayDeque<>();
ListNode temp = curr;
int count = 0;
while (temp != null && count < k) {
stack.push(temp);
temp = temp.next;
count++;
}
// 不足 k 个节点，直接把剩余节点接到结果链表末尾
if (count < k) {
tail.next = curr;
break;
}
// 恰好 k 个节点，出栈（即翻转顺序）接到结果链表
while (!stack.isEmpty()) {
tail.next = stack.pop();
tail = tail.next;
}
tail.next = null; // 防止成环，临时断开
// curr 移动到下一组的起始节点
curr = temp;
}
return dummy.next;
}
}复杂度分析
- 时间复杂度：O(n)。每个节点被访问常数次（压栈一次，出栈一次）。
- 空间复杂度：O(k)。栈最多存 k 个节点，但由于每次处理完都清空，空间是 O(k) 而不是 O(n)。
适用场景
理解题意、验证逻辑时很好用。面试中如果一时想不到最优解，先写这个展示思路，然后继续优化。注意空间是 O(k)，不符合进阶要求的 O(1)。
三、解法二：优化解法——递归分组
思路
递归思路非常自然：
- 先检查当前组是否有 K 个节点可用
- 如果有，翻转这 K 个节点，然后把翻转后组的尾节点连接到"递归处理剩余链表"的结果
- 如果不足 K 个，直接返回 head（保持原顺序）
翻转 K 个节点的子过程就是 LeetCode 206 反转整个链表的逻辑，套用即可。
完整代码
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
// 检查从 head 开始是否有 k 个节点
ListNode check = head;
int count = 0;
while (check != null && count < k) {
check = check.next;
count++;
}
// 不足 k 个节点，直接返回，保持原顺序
if (count < k) {
return head;
}
// 翻转前 k 个节点，check 此时指向第 k+1 个节点
ListNode prev = null;
ListNode curr = head;
for (int i = 0; i < k; i++) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
// 翻转完成：prev 是新头节点，head 是新尾节点（即原头节点）
// 递归处理剩余链表，把结果接到当前组的尾节点
head.next = reverseKGroup(curr, k);
// prev 是当前翻转组的头节点
return prev;
}
}复杂度分析
- 时间复杂度：O(n)。每个节点被访问两次（一次检查，一次翻转）。
- 空间复杂度：O(n/k)。递归调用栈深度为 n/k（每 K 个节点一次递归调用）。当 k=1 时退化为 O(n)，当 k=n 时为 O(1)。
适用场景
代码清晰，逻辑易懂，是理解这道题的最佳入口。面试中先写这个版本，再提出迭代版本优化空间，体现了从清晰到优化的完整思考过程。
四、解法三：最优解法——O(1) 空间纯迭代
思路
迭代版本要达到 O(1) 空间，核心挑战是"如何在不递归的情况下，把每组反转后的节点正确接入整体链表"。
关键在于维护好两个连接点：
groupPrev：当前组的前一个节点（反转后需要groupPrev.next = 当前组的新头节点）groupEnd：当前组的最后一个节点（反转后需要groupEnd.next = 下一组的起始节点）
以 [1,2,3,4,5]，k=3 为例：
第一组（节点1,2,3）：
groupPrev = dummy- 找到组尾
groupEnd = 节点3，记录nextGroupStart = 节点4 - 反转 [1,2,3]，得到 [3,2,1]
- 连接：
dummy.next = 3，1.next = 4（原头变尾，接下一组）
第二组（节点4,5）：
- 只剩2个节点，不足K=3，直接退出循环
结果：dummy -> 3 -> 2 -> 1 -> 4 -> 5
Mermaid 图——迭代过程
完整代码
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode groupPrev = dummy;
while (true) {
// 找到当前组的第 k 个节点（组尾）
ListNode groupEnd = getKthNode(groupPrev, k);
// 不足 k 个节点，结束
if (groupEnd == null) break;
// 记录下一组的起始节点
ListNode nextGroupStart = groupEnd.next;
// 反转当前组 [groupPrev.next ... groupEnd]
ListNode prev = nextGroupStart; // 尾节点的 next 要接下一组
ListNode curr = groupPrev.next;
while (curr != nextGroupStart) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
// 反转完成：prev 是当前组新头节点（原组尾），groupPrev.next 是当前组新尾节点（原组头）
// 把当前组接回主链表
ListNode oldGroupHead = groupPrev.next; // 反转前的组头 = 反转后的组尾
groupPrev.next = groupEnd; // groupPrev 接新组头（原组尾）
oldGroupHead.next = nextGroupStart; // 新组尾接下一组起始
// groupPrev 更新为当前组的新尾节点（即原来的组头），为下一轮做准备
groupPrev = oldGroupHead;
}
return dummy.next;
}
// 从 node 出发，找到第 k 个节点；不足 k 个返回 null
private ListNode getKthNode(ListNode node, int k) {
while (node != null && k > 0) {
node = node.next;
k--;
}
return node;
}
}复杂度分析
- 时间复杂度：O(n)。
getKthNode每次 O(k)，反转每次 O(k)，共 n/k 组，总计 O(n)。 - 空间复杂度：O(1)。只用了常数个指针变量，没有递归栈，满足进阶要求。
适用场景
面试进阶问题标准答案，也是生产代码首选。掌握这个版本意味着你真正理解了链表指针操作的精髓。
提交结果：时间击败约 99% 用户，空间击败约 95% 用户。
五、举一反三
同类题目
LeetCode 24. 两两交换链表中的节点 K=2 的特殊情况，可以用本题代码直接处理（传 k=2），也可以专门优化。
LeetCode 92. 反转链表 II 本题的单区间版本，只反转一次。
LeetCode 206. 反转链表 K=n 的特殊情况。
LeetCode 2074. 反转偶数长度组的节点 需要先判断每组长度的奇偶性再决定是否反转，是本题的变体。
解题模板
K组处理的通用迭代框架：
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode groupPrev = dummy;
while (true) {
// 1. 检查是否有足够的节点（getKthNode）
ListNode groupEnd = getKthNode(groupPrev, k);
if (groupEnd == null) break;
// 2. 保存下一组起点
ListNode nextStart = groupEnd.next;
// 3. 反转当前组
// ...（参考解法三中的反转逻辑）
// 4. 重新连接：更新 groupPrev
groupPrev = /* 当前组的新尾节点 */;
}
return dummy.next;六、踩坑实录
坑一：检查节点数量时多走了一步
有人这样写检查：
// 错误写法
ListNode check = head;
for (int i = 0; i < k; i++) {
if (check == null) return head; // 这里提前返回了
check = check.next;
}这个写法会在 count 恰好等于 k 时多走一步，导致 check 指向第 k+1 个节点而不是第 k 个节点。需要注意循环条件和退出时机。
坑二：反转后忘记把尾节点接到下一组
递归版本把这一步隐藏在 head.next = reverseKGroup(curr, k) 中了，很自然。迭代版本需要手动处理 oldGroupHead.next = nextGroupStart，这行如果漏了，尾节点的 next 指向会残留旧的值，导致链表断裂或成环。
坑三：groupPrev 更新错位
每次处理完一组后，groupPrev 要更新为当前组的新尾节点（即原来的组头节点），为下一轮的连接做准备。如果更新为了新的组头（原组尾），下一轮 groupPrev.next 就跳过了下一组，导致跳组。
坑四：最后一组不足K个时节点被漏处理
用递归版本时，count < k 时返回 head，这是正确的。但用迭代版本时，break 后 groupPrev 还指向上一组的尾节点，groupPrev.next 应该已经指向了最后不足 K 个节点的起始节点，这是通过不修改 groupPrev.next 自然保留下来的，不需要额外处理，注意不要画蛇添足。
坑五：哑节点忘记返回 dummy.next
最后一行写成了 return head，但 head 在 k=1 时可能已经不是头节点了。永远返回 dummy.next。
七、总结
25 题是链表题里少有的 Hard，难点不在算法思路，而在工程实现——如何在指针操作密集的情况下保持思路清晰、不出错。
我的建议是：先把递归版本写对，彻底理解每一步在干什么，然后再移植到迭代版本。递归版本逻辑更清晰，是理解题意的最好方式；迭代版本是面试进阶追问的标准答案，O(1) 空间是关键。
这三道题——206、92、25——连起来刷，代表了链表反转操作从简单到复杂的完整路径。吃透这三道，后面遇到链表反转变体基本上都能搞定。
三道链表反转连刷，你更喜欢哪种写法？递归还是迭代？评论区聊聊，点个在看支持一下。