25、K个一组翻转链表
25、 K 个一组翻转链表
鲁迅说，LeetCode 官方这道题的题目是 K 个一组翻转链表，怎么看怎么别扭，
不是我太敏感了（ ）。 ?
我觉得应该是 K 个一组，翻转链表 或者 翻转链表 K 个 一
组
。缺
少断
句
，不
知道
是
题意
给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那请将
最后剩余的节点保持原有顺序。
注：你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
难度
困难
示例
025.K%E4%B8%AA%E4%B8%80%E7%BB%84%E7%BF%BB%E8%BD%AC%E9%93%BE%
E8%A1%A8-20240207173433.png
输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]
k=2，反转的是
• 1,2 → 2,1
• 3,4 → 4,3
• 5（只有一位了，不是 k 的整数倍，保留原样）
025.K%E4%B8%AA%E4%B8%80%E7%BB%84%E7%BF%BB%E8%BD%AC%E9%93%BE%
E8%A1%A8-20240207173510.png
输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]
k=3，反转的是
• 1,2,3 → 3,2,1
• 4,5（只有 2 位了，不是 k 的整数倍，保留原样）
分析
由于我们刚刚解完 024.两两交换链表中的节点 这道题，所以面对本题时，虽然是 hard 难
度，但并不会被它吓到。
比如说，当 k=2 时，其实就是两两交换链表中的节点，只不过，这道题，可能是两两交
换，也可能是三三交换，也可能是四四交换，也可能是五五交换……
两两交换、三三交换、四四交换……这些其实就是翻转链表：给你一个有 k 个节点的链
表，翻转它。
025.K%E4%B8%AA%E4%B8%80%E7%BB%84%E7%BF%BB%E8%BD%AC%E9%93%BE%
E8%A1%A8-20240207182228.png
OK，我们试着来解这道题。
public ListNode reverseList(ListNode head) {
ListNode prev = null; // 翻转链表的新头初始化为 null
ListNode curr = head; // 当前节点设置为头节点
while (curr != null) {
ListNode nextTemp = curr.next; // 保存当前节点的下一个节点
curr.next = prev; // 翻转当前节点的指向
prev = curr; // 更新 prev 为当前节点
curr = nextTemp; // 移动当前节点到下一个节点
}
return prev; // 返回翻转后的链表头
}
假设我们有一个链表：
1 -> 2 -> 3 -> 4 -> null
目标是将其翻转为：
4 -> 3 -> 2 -> 1 -> null
我们需要设置两个指针：prev 和 curr。
• prev 指针初始设置为 null，因为翻转后的链表的第一个节点（原链表的最后一个节
点）将指向 null。
• curr 指针初始设置为 head，即链表的第一个节点。
我们开始遍历链表，对于链表中的每一个节点：
①、保存下一个节点：首先，我们需要保存 curr 节点的下一个节点，因为一旦我们改变
curr 的指向，就会失去访问它原来的下一个节点的方式。这可以通过一个临时变量
nextTemp 实现。
ListNode nextTemp = curr.next;
②、翻转指向：接着，我们将 curr 的 next 指向 prev，这是实现翻转的关键步骤。
curr.next = prev;
③、移动 **prev**** 和 ****curr**：完成上述操作后，我们需要更新 prev 和 curr 指
针，以便继续遍历链表。prev 移动到 curr 的位置，curr 则移动到 nextTemp 的位置。
prev = curr;
curr = nextTemp;
这个过程一直重复，直到 curr 为 null，即达到链表的末尾。此时，prev 指向的是翻转后
的链表的头节点。
完成遍历后，prev 指向的就是翻转后的链表的头节点。
搞定翻转链表的方法后，本题“K 个一组翻转链表”我们就完成了一半了。接下来，我们只
需要找出 K 个节点的链表，然后调用翻转链表的方法即可。对吧？
025.K%E4%B8%AA%E4%B8%80%E7%BB%84%E7%BF%BB%E8%BD%AC%E9%93%BE%
E8%A1%A8-20240207183553.png
好，我们来解这道题：找出 K 个节点的链表。
public ListNode findK(ListNode head, int k) {
ListNode tail = head;
for (int i = 1; i < k; i++) {
tail = tail.next;
}
return tail;
}
这个方法很简单，for 循环遍历链表，找到第 k 个节点，返回即可。
OK，我们来总结一下本题：
1. 找出 k 个待翻转的节点，如果不足 k 个，则不做翻转，直接返回。
2. 翻转这 k 个节点，并且获取反转后的第一个节点（也就是翻转前的最后一个节点）
3. 若后面的节点能够翻转，则继续翻转，即，对后方的 k 个节点继续进行 1、2 操作
4. 返回先前获取的第一个节点
/**
* 定义一个简单的链表.
* 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) {
// 初始化 tail 用于遍历找到第 k 个节点
ListNode tail = head;
for (int i = 1; i <= k; i++) {
// 如果不足 k 个，则不进行翻转，直接返回原链表头部
if (tail == null) return head;
tail = tail.next;
}
// 翻转当前 k 个元素的链表，并返回新的头节点
ListNode newHead = reverse(head, tail);
// 递归处理剩下的链表，并将当前翻转的链表的尾部（原 head）连接到翻转后的剩余链表
上
head.next = reverseKGroup(tail, k);
return newHead;
}
private ListNode reverse(ListNode head, ListNode tail) {
ListNode prev = null;
ListNode next;
while (head != tail) {
// 保存当前节点的下一个节点
next = head.next;
// 将当前节点的 next 指向 prev，完成翻转
head.next = prev;
// prev 和 head 前进一位
prev = head;
head = next;
}
// 返回翻转后的链表的头节点
return prev;
}
}
详细解释一下个题解：
• 遍历寻找第 k 个节点：使用 tail 变量从当前的 head 开始遍历，寻找第 k 个节点。这
个过程中如果发现节点数不足 k 个（即 tail 变为 null），则直接返回原始的 head 节
点，因为题目要求不足 k 个节点的部分不需要翻转。
• 翻转当前的 k 个节点：调用 reverse 方法，传入当前的 head 和 tail，
tail 是第 k+1 个节
点，但不包括在翻转范围内（左闭右开区间 [head, tail)）。翻转完成后返回新的头
节点，即原来 k 个节点的最后一个节点。
• 递归处理剩余部分：递归调用 reverseKGroup 方法处理剩余的链表部分。由于翻转后
原来的 head 节点变成了当前翻转部分的尾节点，所以将其 next 指向递归调用的结
果，以此来连接后续翻转后的链表。
• reverse 方法：翻转链表的方法，多了一个 tail 参数，用于控制翻转的范围。
当输入 head = [1,2,3,4,5] 和 k = 4 时，我们来模拟一下整个题解过程：
初始状态：
链表为 1 -> 2 -> 3 -> 4 -> 5，我们需要每 4 个节点作为一组进行翻转。
第一次调用 reverseKGroup：
• 我们尝试找到第 4 个节点，即节点 4。由于我们能成功找到第 4 个节点，这意味着这
一组有足够的节点进行翻转。
• 我们调用 reverse 方法，以节点 1 作为 head，节点 5 作为 tail（不包含在翻转
中），进行翻转。
• 翻转后的链表变为 4 -> 3 -> 2 -> 1 -> null，此时 1 的 next 指向 null，等待连接剩
余部分的翻转结果。
递归调用 reverseKGroup 处理剩余部分：
• 剩余部分为 [5]，因为只有一个节点，不足 k 个，所以直接返回该部分。
• 我们将节点 1（翻转后的尾部）的 next 指向这个剩余部分，即节点 5。
最终结果：
• 连接后的最终链表为 4 -> 3 -> 2 -> 1 -> 5。
• 在这个过程中，第一组的四个节点被翻转，而最后一个节点保持不变，因为它不满足
翻转的节点数量要求。
整个题解的效率也非常优秀：
025.K%E4%B8%AA%E4%B8%80%E7%BB%84%E7%BF%BB%E8%BD%AC%E9%93%BE%
E8%A1%A8-20240207184844.png
总结
这道题的难度是 hard，但是我们通过分析题目，将其拆解成了两个简单的问题：翻转链
表和找出 K 个节点的链表。这样，我们就可以轻松解决这道题了。
涉及到的 Java 基础知识，包括：
• 链表
• 循环
• 递归，这部分可以通过这个视频深度理解一下
025.K%E4%B8%AA%E4%B8%80%E7%BB%84%E7%BF%BB%E8%BD%AC%E9%93%BE%
E8%A1%A8-20240207185945.png
力扣链接：https://leetcode.cn/problems/reverse-nodes-in-k-group/