图解：K 个一组翻转链表 | LeetCode 级别：困难
一. 序
链表作为一种基本的数据结构，本身理解起来很简单。它通过指针，将一组零散的内存空间（结点），串联起来，组成一个数据结构。
在面试的算法题中，经常会碰到链表相关的面试题。虽然链表的结构比较好理解，但是链表的题还是比较考验代码能力的。一些单链表的题，指针指来指去，很容易就把结点的 next 指针弄丢了，造成链表断裂。
链表翻转是一个面试中经常会碰到的题，在之前的文章中，也聊过单链表翻转、链表双双翻转（点击蓝字可跳转了解），今天再来聊聊它们的「升级版」，以 K 个为一组，翻转链表，同时这也是 LeetCode 的第 25 题。
二. K 个一组翻转链表
以 K 个结点为一组，将给定的单链表进行翻转。有点类似之前的链表两两翻转，只是那时的 K = 2。而在这道题中，K 变成一个外部传入的正整数，它是一个可变的值，并且小于或者等于链表的长度。
这道算法题，会用到之前的知识，既然 K 是可变的，我们无法估计 K 的大小，但是我们可以将原始链表，以 K 个结点为一组，执行单链表翻转的逻辑。
这就要用到之前《单链表翻转》的技巧了，不了解的建议先读读之前的文章。
既然需要将原始链表先以 K 个结点分组，再依次执行单链表翻转，在每组字链表翻转之后，还需要将它们再串起来，否则链表不就断裂了么。
这就需要使用两个变量 prev 和 end，分别记录子链表的前驱结点，以及子链表的尾结点。有了 end 这个子链表的尾结点，就可以很容易通过 end.next 拿到下一个子链表的头结点。
依据这几个结点，就可以完成子链表的翻转，以及保证在子链表翻转后依然可以串起来。
另外有一个特殊处理的地方，当原始链表以 K 个结点为一组分组时，末尾不满一组的子链表，保持原样不进行翻转。
参考链表两两翻转的思路，为了保证我们的代码逻辑统一，我们增加一个虚拟的头结点 dummy，来方便我们编写代码。
直接上代码，细节都在注释里。
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
// 增加虚拟头结点
ListNode dummy = new ListNode(0);
dummy.next = head;
// 定义 prev 和 end 结点
ListNode prev = dummy;
ListNode end = dummy;
while(end.next != null) {
// 以 k 个结点为条件，分组子链表
for (int i = 0; i < k && end != null; i++)
end = end.next;
// 不足 K 个时不处理
if (end == null)
break;
// 处理子链表
ListNode start = prev.next;
ListNode next = end.next;
end.next = null;
// 翻转子链表
prev.next = reverseList(start);
// 将子连表前后串起来
start.next = next;
prev = start;
end = prev;
}
return dummy.next;
}
// 递归完成单链表翻转
private ListNode reverseList(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode p = reverseList(head.next);
head.next.next = head;
head.next = null;
return p;
}
}
这里单链表的翻转，使用了递归，一般 K 值都不会太大，所以用递归没问题，当然你也可以换成循环实现。对细节不了解的，可以参见《单链表翻转》。
三. 小结时刻
到这里单链表，按 K 分组翻转的具体思路和代码，就介绍清楚了。我这种处理方式可能不是最高效的，但是应该是比较清晰的。
另外在实际面试中，其实很多场景下，都不会直接出 leetcode 上的算法题，都会稍微变种一下，但是大家要学会将复杂问题，转化为简单问题来解决。
到这里，链表翻转的基础题，基本上就说清楚了，包含三个篇文章：
今天就到这里，有任何问题欢迎留言讨论。
本文对你有帮助吗？留言、转发、点好看是最大的支持，谢谢！
「联机圆桌」👈推荐我的知识星球，一年 50 个优质问题，上桌联机学习。
公众号后台回复成长『成长』，将会得到我准备的学习资料。