025.K 个一组翻转链表

作者：沉默王二
发布时间：2024-02-08T15:33:41.187+0800

鲁迅说，LeetCode 官方这道题的题目是 K 个一组翻转链表，怎么看怎么别扭，我觉得应该是 K 个一组，翻转链表或者翻转链表 K 个一组。缺少断句，不知道是不是我太敏感了（😂）。

技术派阅读地址：https://paicoding.com/column/7/25

语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu
这道题可以说完全重写了，给出 2 道大家完全都能掌握的题解（递归和 while 循环）。
增加代码注释，这样大家更容易看懂并掌握题解；
增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；
增加手绘图，这样大家更容易理解解题思路；
增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；
增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；
图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。
另外，这一版本会作为 PDF 的终稿随后在星球进行发布。

题意

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那请将最后剩余的节点保持原有顺序。

注：你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

难度

困难

示例

输入：head = [1,2,3,4,5], k = 2

k=2，反转的是

1,2 → 2,1
3,4 → 4,3
5（只有一位了，不是 k 的整数倍，保留原样）

输入：head = [1,2,3,4,5], k = 3

k=3，反转的是

1,2,3 → 3,2,1
4,5（只有 2 位了，不是 k 的整数倍，保留原样）

分析

由于我们刚刚解完 024.两两交换链表中的节点 这道题，所以面对本题时，虽然是 hard 难度，但并不会被它吓到。

比如说，当 k=2 时，其实就是两两交换链表中的节点，只不过，这道题，可能是两两交换，也可能是三三交换，也可能是四四交换，也可能是五五交换……

两两交换、三三交换、四四交换……这些其实就是翻转链表：给你一个有 k 个节点的链表，翻转它。

OK，我们试着来解这道题。

public ListNode reverseList(ListNode head) {

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 为 null，即达到链表的末尾。此时，prev 指向的是翻转后的链表的头节点。

完成遍历后，prev 指向的就是翻转后的链表的头节点。

搞定翻转链表的方法后，本题“K 个一组翻转链表”我们就完成了一半了。接下来，我们只需要找出 K 个节点的链表，然后调用翻转链表的方法即可。对吧？

好，我们来解这道题：找出 K 个节点的链表。

public ListNode findK(ListNode head, int k) {

for (int i = 1; i < k; i++) {        tail = tail.next;    }    return tail;}

这个方法很简单，for 循环遍历链表，找到第 k 个节点，返回即可。

OK，我们来总结一下本题：

找出k个待翻转的节点，如果不足k个，则不做翻转，直接返回。
翻转这k个节点，并且获取反转后的第一个节点（也就是翻转前的最后一个节点）
若后面的节点能够翻转，则继续翻转，即，对后方的k个节点继续进行1、2操作
返回先前获取的第一个节点

/**

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。
在这个过程中，第一组的四个节点被翻转，而最后一个节点保持不变，因为它不满足翻转的节点数量要求。

整个题解的效率也非常优秀：

总结

这道题的难度是 hard，但是我们通过分析题目，将其拆解成了两个简单的问题：翻转链表和找出 K 个节点的链表。这样，我们就可以轻松解决这道题了。

涉及到的 Java 基础知识，包括：

力扣链接：https://leetcode.cn/problems/reverse-nodes-in-k-group/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

该题解目前只针对**二哥编程星球 **的球友开放，如果你也想一起打卡学习算法的话，扫下面的优惠券加入我们吧，星球目前 4300+ 人，定价 149 元，从当初的 99 元一路涨上来的，所以早就是优势，别再犹豫了。

（优惠券仅 300 张，数量有限）

一个人可以走得很快，但一群人才能走得更远。如果想去面中大厂的话，LeetCode 几乎是必刷的，二哥的 LeetCode 题解通俗易懂、图文并茂，理解给你举一反三的解题能力，冲鸭。

技术派阅读地址：https://paicoding.com/column/7/25

语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu
这道题可以说完全重写了，给出 2 道大家完全都能掌握的题解（递归和 while 循环）。
增加代码注释，这样大家更容易看懂并掌握题解；
增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；
增加手绘图，这样大家更容易理解解题思路；
增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；
增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；
图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。
另外，这一版本会作为 PDF 的终稿随后在星球进行发布。

题意

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那请将最后剩余的节点保持原有顺序。

注：你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

难度

困难

示例

输入：head = [1,2,3,4,5], k = 2

k=2，反转的是

1,2 → 2,1
3,4 → 4,3
5（只有一位了，不是 k 的整数倍，保留原样）

输入：head = [1,2,3,4,5], k = 3

k=3，反转的是

1,2,3 → 3,2,1
4,5（只有 2 位了，不是 k 的整数倍，保留原样）

分析

由于我们刚刚解完 024.两两交换链表中的节点 这道题，所以面对本题时，虽然是 hard 难度，但并不会被它吓到。

两两交换、三三交换、四四交换……这些其实就是翻转链表：给你一个有 k 个节点的链表，翻转它。

OK，我们试着来解这道题。

public ListNode reverseList(ListNode head) {

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，即链表的第一个节点。

我们开始遍历链表，对于链表中的每一个节点：

ListNode nextTemp=curr.next;

②、翻转指向：接着，我们将 curr 的 next 指向 prev，这是实现翻转的关键步骤。

curr.next=prev;

③、移动 prev 和 curr：完成上述操作后，我们需要更新 prev 和 curr 指针，以便继续遍历链表。prev 移动到 curr 的位置，curr 则移动到 nextTemp 的位置。

prev=curr;

这个过程一直重复，直到 curr 为 null，即达到链表的末尾。此时，prev 指向的是翻转后的链表的头节点。

完成遍历后，prev 指向的就是翻转后的链表的头节点。

好，我们来解这道题：找出 K 个节点的链表。

public ListNode findK(ListNode head, int k) {

for (int i = 1; i < k; i++) {        tail = tail.next;    }    return tail;}

这个方法很简单，for 循环遍历链表，找到第 k 个节点，返回即可。

OK，我们来总结一下本题：

找出k个待翻转的节点，如果不足k个，则不做翻转，直接返回。
翻转这k个节点，并且获取反转后的第一个节点（也就是翻转前的最后一个节点）
若后面的节点能够翻转，则继续翻转，即，对后方的k个节点继续进行1、2操作
返回先前获取的第一个节点

/**

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。
在这个过程中，第一组的四个节点被翻转，而最后一个节点保持不变，因为它不满足翻转的节点数量要求。

整个题解的效率也非常优秀：

总结

这道题的难度是 hard，但是我们通过分析题目，将其拆解成了两个简单的问题：翻转链表和找出 K 个节点的链表。这样，我们就可以轻松解决这道题了。

涉及到的 Java 基础知识，包括：

力扣链接：https://leetcode.cn/problems/reverse-nodes-in-k-group/

一步一个脚印

（优惠券仅 300 张，数量有限）

技术派阅读地址：https://paicoding.com/column/7/25

语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu
这道题可以说完全重写了，给出 2 道大家完全都能掌握的题解（递归和 while 循环）。
增加代码注释，这样大家更容易看懂并掌握题解；
增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；
增加手绘图，这样大家更容易理解解题思路；
增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；
增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；
图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。
另外，这一版本会作为 PDF 的终稿随后在星球进行发布。

题意

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那请将最后剩余的节点保持原有顺序。

注：你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

难度

困难

示例

输入：head = [1,2,3,4,5], k = 2

k=2，反转的是

1,2 → 2,1
3,4 → 4,3
5（只有一位了，不是 k 的整数倍，保留原样）

输入：head = [1,2,3,4,5], k = 3

k=3，反转的是

1,2,3 → 3,2,1
4,5（只有 2 位了，不是 k 的整数倍，保留原样）

分析

由于我们刚刚解完 024.两两交换链表中的节点 这道题，所以面对本题时，虽然是 hard 难度，但并不会被它吓到。

两两交换、三三交换、四四交换……这些其实就是翻转链表：给你一个有 k 个节点的链表，翻转它。

OK，我们试着来解这道题。

public ListNode reverseList(ListNode head) {

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，即链表的第一个节点。

我们开始遍历链表，对于链表中的每一个节点：

ListNode nextTemp=curr.next;

②、翻转指向：接着，我们将 curr 的 next 指向 prev，这是实现翻转的关键步骤。

curr.next=prev;

③、移动 prev 和 curr：完成上述操作后，我们需要更新 prev 和 curr 指针，以便继续遍历链表。prev 移动到 curr 的位置，curr 则移动到 nextTemp 的位置。

prev=curr;

这个过程一直重复，直到 curr 为 null，即达到链表的末尾。此时，prev 指向的是翻转后的链表的头节点。

完成遍历后，prev 指向的就是翻转后的链表的头节点。

好，我们来解这道题：找出 K 个节点的链表。

public ListNode findK(ListNode head, int k) {

for (int i = 1; i < k; i++) {        tail = tail.next;    }    return tail;}

这个方法很简单，for 循环遍历链表，找到第 k 个节点，返回即可。

OK，我们来总结一下本题：

找出k个待翻转的节点，如果不足k个，则不做翻转，直接返回。
翻转这k个节点，并且获取反转后的第一个节点（也就是翻转前的最后一个节点）
若后面的节点能够翻转，则继续翻转，即，对后方的k个节点继续进行1、2操作
返回先前获取的第一个节点

/**

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。
在这个过程中，第一组的四个节点被翻转，而最后一个节点保持不变，因为它不满足翻转的节点数量要求。

整个题解的效率也非常优秀：

总结

这道题的难度是 hard，但是我们通过分析题目，将其拆解成了两个简单的问题：翻转链表和找出 K 个节点的链表。这样，我们就可以轻松解决这道题了。

涉及到的 Java 基础知识，包括：

力扣链接：https://leetcode.cn/problems/reverse-nodes-in-k-group/

一步一个脚印

（优惠券仅 300 张，数量有限）

            知识星球
            
    
    
        
        扫码加入星球
        查看更多优质内容
    
    https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412