题目导航
【Leetcode Hot 100刷题路线】| 找工作速刷 | 第19题 – [25] – K 个一组翻转链表
难度：困难 tags：链表、反转、递归
题目描述
给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
示例 1： 
输入：head = [1,2,3,4,5], k = 2 输出：[2,1,4,3,5]
示例 2： 
输入：head = [1,2,3,4,5], k = 3 输出：[3,2,1,4,5]
题解
如果你已经掌握了反转链表 I、反转链表 II，那么 K 个一组翻转链表就是它们的自然延伸。
主要思路：把链表切成若干段，每段 k 个节点，分别反转
想象你有一条长长的链表，现在要把它切成若干段，每段正好 k 个节点，然后把每一段内部的箭头全部掉头，最后再把所有段按顺序连起来。
但这里有个细节：如果最后一段不足 k 个节点，就保持原样，不反转。
为了方便描述，我们依然用之前引入的哨兵节点 dummy 和 p0 指针，p0 永远指向待反转段的前一个节点。
第一步：统计链表长度，确定需要反转的组数
我们需要知道链表总共有多少个节点，以便判断能分成几组。 用一个指针遍历链表，统计长度 n，然后需要反转的组数就是 n / k（向下取整）。
int n = 0;
ListNode temp = head;
while (temp != null) {
n++;
temp = temp.next;
}
之后我们将用 p0 = dummy 开始处理每一组。
第二步：在每一组内部反转 k 个节点
这一步其实和 反转链表I 一模一样,我们只需要在每一组内执行 k 次箭头掉头操作。
回忆一下反转整个链表的经典代码（pre 初始为 null，cur 为第一个节点）：
ListNode pre = null;
ListNode cur = 组内第一个节点;
while (循环 k 次) {
ListNode nxt = cur.next; // 保存下一个节点
cur.next = pre; // 掉头
pre = cur; // pre 前进
cur = nxt; // cur 前进
}
在本题中，组内第一个节点就是 p0.next，我们把它记为 start。 反转 k 个节点后，pre 会指向反转后的头结点（即原组的最后一个节点），cur 会指向下一组的第一个节点（即原组后面紧跟着的节点）。
第三步：将反转后的组前后连接
反转完一组后，链表实际上被切成了三段：
-
p0 之前的部分（已经处理完）
-
刚刚反转完的这一组（头是 pre，尾是原来的 start）
-
cur 之后的部分（待处理或保留）
我们需要把这三段重新连接起来，连接顺序非常重要：
p0.next.next = cur; / p0.next 就是 start，反转后它变成了尾部
p0.next = pre;
p0 = start; / 或者 p0 = p0.next; 因为 p0.next 已经变成了 pre，但我们需要的是原来的 start
实际上，我们在反转前已经保存了 start = p0.next，所以这里直接用 p0 = start。
第四步：重复处理下一组
每处理完一组，就更新 p0 到新位置，然后继续对下一组进行反转。 直到处理完 n/k 组，剩下的节点（不足 k 个）保持原样，不处理。
演示
我们以 head = [1,2,3,4,5,6,7], k = 3 为例，手动模拟一下前两组的处理过程。
初始状态
dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> null
p0
链表长度 n = 7，需要反转的组数 = 7/3 = 2 组（前两组反转，最后一组剩 1 个不反转）。
1. 第 1 组反转前
dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> null
p0 ↑
start = p0.next
pre = null, cur = start = 1
反转过程（k=3 次循环）：
第一次循环：
-
nxt = cur.next = 2
-
cur.next = pre (null) → 1 -> null
-
pre = cur (1)
-
cur = nxt (2)
结果
dummy 1 -> null 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> null
↑ ↑
p0 pre cur
第二次循环：
-
nxt = cur.next = 3
-
cur.next = pre (1) → 2 -> 1 -> null
-
pre = cur (2)
-
cur = nxt (3)
dummy 2 -> 1 -> null 3 -> 4 -> 5 -> 6 -> 7 -> null
↑ ↑
p0 pre cur
第三次循环：
-
nxt = cur.next = 4
-
cur.next = pre (2) → 3 -> 2 -> 1 -> null
-
pre = cur (3)
-
cur = nxt (4)
dummy 3 -> 2 -> 1 -> null 4 -> 5 -> 6 -> 7 -> null
↑↑
p0 pre cur
反转完成，此时 pre 指向本组新头部（3），cur 指向下一组第一个节点（4），start 仍然是原来的 1（现在在尾部）。
连接：
-
p0.next.next = cur → 1.next = 4（因为 p0.next 是 1）
-
p0.next = pre → dummy.next = 3
-
移动 p0 到本组尾部：p0 = start = 1（现在 1 是尾部，它的 next 已经是 4）
dummy -> 3 -> 2 -> 1 -> 4 -> 5 -> 6 -> 7 -> null
↑
p0
2. 第 2 组反转前 此时 p0 指向 1（上一组的尾部），start = p0.next = 4。
开始第二组反转（同样 k=3 次循环），过程与第一组完全相同，不再赘述。
反转后：
dummy -> 3 -> 2 -> 1 -> 6 -> 5 -> 4 -> 7 -> null
↑ ↑ ↑
p0 pre cur
这里 pre 指向 6，cur 指向 7，start 是原来的 4（现在在尾部）。
连接：
-
p0.next.next = cur → 4.next = 7
-
p0.next = pre → 1.next = 6
-
移动 p0 到本组尾部：p0 = start = 4
dummy -> 3 -> 2 -> 1 -> 6 -> 5 -> 4 -> 7 -> null
↑
p0
此时已处理完 2 组（n/k = 2），剩余节点不足 k 个，保持原样。最终链表就是 [3,2,1,6,5,4,7]。
可以看到，反转链表 I、反转链表 II、K 个一组翻转链表这三道题的核心都是箭头掉头 + 拼接，区别在于：
-
反转链表 I：一次性处理整个链表。
-
反转链表 I：处理连续的一段，用 p0 固定左边界。
-
K 个一组翻转链表：处理多段，每段结束后移动 p0 到新位置。
代码（Java版）
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
// 1. 统计链表长度
int n = 0;
ListNode temp = head;
while (temp != null) {
n++;
temp = temp.next;
}
// 2. 设置哨兵节点
ListNode dummy = new ListNode(0, head);
ListNode p0 = dummy; // p0 始终指向待处理组的前一个节点
ListNode cur = p0.next;
ListNode pre = null;
// 3. 循环处理每一组（一共 n/k 组）
while (n >= k) {
// 组内反转 k 个节点
for (int i = 0; i < k; i++) {
ListNode nxt = cur.next;
cur.next = pre;
pre = cur;
cur = nxt;
}
// 此时 pre 指向本组新头部，cur 指向下一组第一个节点
// 保存本组原来的第一个节点（现在变成尾部）
ListNode start = p0.next;
// 先让本组尾部指向下一组开头
p0.next.next = cur;
// 再让 p0 指向本组新头部
p0.next = pre;
// 移动 p0 到本组尾部（即原来的 start），为下一组做准备
p0 = start;
n -= k; // 剩余节点数减少 k
}
return dummy.next;
}
}
