一、题目描述
将给出的链表中的结点每 k 个一组翻转，返回翻转后的链表。
如果链表中的结点数不是 k 的倍数，将最后剩下的结点保持原样。
你不能更改结点中的值，只能更改结点本身。
二、题目解析
对于这道题目，如果一开始摸不清思路，可以先模拟看看，以 k 为 3 作为示例。
通过上图可以注意到，每次操作的过程实际上就是在翻转准备翻转链表的区域，把这个区域的所有结点都翻转成功之后，再连接到已经翻转区域链表的区域尾部，然后再继续去还未翻转的区域里面寻找出 k 个结点来继续操作。
完整的操作可以查看下方的动画。
接下来，我们从头到尾模拟一下这个过程是怎么操作的。
1、对于原链表来说，除了头结点之外，其余的所有结点都有前面一个结点指向它，那么为了避免在操作这些结点（比如移动、删除操作）过程中需要判断当前结点是否是头结点，可以在原链表的前面增加一个虚拟结点，这样就可以使得原链表里面的所有结点的地位都是一样的了。
2、接下来，设置两个指针，都指向虚拟头结点的位置，一个指针是 pre，它在后续的操作过程中会始终指向每次要翻转的链表的头结点的【上一个结点】，另外一个指针是 end，它在后续的操作过程中会始终指向每次要翻转的链表的尾结点。
3、以 k 为 3 作为示例，那么 pre 和 end 不断的向后移动，当 end 来到 3 这个结点的时候，已经寻找出来需要翻转的那 3 个结点，并且 pre 依旧指向 dummy，因为 1 这个结点是翻转区域的头结点，前面那个则是上一个结点，因此 pre 还停留在原地。
4、那么需要去翻转 1 、2 、3 这个结点，为了避免翻转过程会影响其它区域的结点，这个时候就需要把翻转区域和其它区域断开连接，同时又为了保证翻转成功之后能顺利连接回去，因此需要记录一下后续的结点，这个结点也就是 end.next ，接下来再断开准备翻转链表区域的前后区域，如下图所示。
5、而 1 、2 、3 的翻转过程可以直接套用反转链表这题的思路和代码。
6、该区域的结点翻转成功之后，连接回去，回到第 2 点提到的 pre 这个指针是始终指向每次要翻转的链表的头结点的【上一个结点】，实际上也就是已经翻转区域的尾结点位置，所以 pre 需要来到 end 的位置，即 1 这个结点位置。
7、接下来，继续让 end 向后移动，找到 k 个结点来。
8、每次 end 寻找出 k 个结点之后，都会执行同样的逻辑，记录接下来需要翻转区域的头结点， 断开前后的区域，翻转本区域的结点，再让 pre 来到 end 的位置，end 来到 start 的位置。
9、最后，直到 end 遍历不到 k 个结点或者指向了 null 的时候也就完成了整个翻转过程。
三、参考代码
import java.util.*;
// 本题文字版详解请访问下方网站
// https://www.algomooc.com
// 作者：程序员吴师兄
public class Solution {
/**
*
* @param head ListNode类
* @param k int整型
* @return ListNode类
*/
public ListNode reverseKGroup (ListNode head, int k) {
// 一开始设置一个虚拟结点，它的值为 -1，它的值可以设置为任何的数，因为我们根本不需要使用它的值
ListNode dummy = new ListNode(-1);
// 虚拟头结点的下一结点指向 head 结点
// 如果原链表是 1 --> 2 --> 3
// 那么加上虚拟头结点就是 -1 --> 1 --> 2 --> 3
dummy.next = head;
// 设置一个指针，指向此时的虚拟结点，pre 表示每次要翻转的链表的头结点的【上一个结点】
// pre: -1 --> 1 --> 2 --> 3
ListNode pre = dummy;
// 设置一个指针，指向此时的虚拟结点，end 表示每次要翻转的链表的尾结点
// end: -1 --> 1 --> 2 --> 3
ListNode end = dummy;
// 通过 while 循环，不断的找到翻转链表的尾部
while ( end.next != null) {
// 通过 for 循环，找到【每一组翻转链表的尾部】
// 由于原链表按照 k 个一组进行划分会可能出现有一组的长度不足 k 个
// 比如原链表 1 --> 2 --> 3 --> 4 --> 5
// k = 2，划分了三组 1 --> 2， 3 --> 4， 5
// 所以得确保 end 不为空才去找它的 next 指针，否则 null.next 会报错
for (int i = 0 ; i < k && end != null ; i++) {
// end 不断的向后移动，移动 k 次到达【每一组翻转链表的尾部】
end = end.next ;
}
// 如果发现 end == null，说明此时翻转的链表的结点数小于 k ，保存原有顺序就行
if (end == null) {
// 直接跳出循环，只执行下面的翻转操作
break;
}
// next 表示【待翻转链表区域】里面的第一个结点
ListNode next = end.next;
// 【翻转链表区域】的最尾部结点先断开
end.next = null ;
// start 表示【翻转链表区域】里面的第一个结点
ListNode start = pre.next;
// 【翻转链表区域】的最头部结点和前面断开
pre.next = null;
// 这个时候，【翻转链表区域】的头结点是 start，尾结点是 end
// 开始执行【反转链表】操作
// 原先是 start --> ...--> end
// 现在变成了 end --> ...--> start
// 要翻转的链表的头结点的【上一个结点】的 next 指针指向这次翻转的结果
pre.next = reverseList(start);
// 接下来的操作是在为【待翻转链表区域】的反转做准备
// 原先是 start --> ...--> end
// 现在变成了 end --> ...--> start
// 【翻转链表区域】里面的尾结点的 next 指针指向【待翻转链表区域】里面的第一个结点
start.next = next ;
// 原先是 start --> ...--> end
// 现在变成了 end --> ...--> start
// pre 表示每次要翻转的链表的头结点的【上一个结点】
pre = start;
// 将 end 重置为【待翻转链表区域】的头结点的上一个结点。
end = start;
}
return dummy.next;
}
private ListNode reverseList(ListNode head) {
// 寻找递归终止条件
// 1、head 指向的结点为 null
// 2、head 指向的结点的下一个结点为 null
// 在这两种情况下，反转之后的结果还是它自己本身
if (head == null || head.next == null) return head;
// 不断的通过递归调用，直到无法递归下去，递归的最小粒度是在最后一个结点
// 因为到最后一个结点的时候，由于当前结点 head 的 next 结点是空，所以会直接返回 head
ListNode cur = reverseList(head.next);
// 比如原链表为 1 --> 2 --> 3 --> 4 --> 5 --> null
// 5 -- > 4
// 第一次执行下面代码的时候，head 为 4，那么 head.next = 5
// 那么 head.next.next 就是 5.next ，意思就是去设置 5 的下一个结点
// 等号右侧为 head，意思就是设置 5 的下一个结点是 4
head.next.next = head;
// head 原来的下一结点指向自己，所以 head 自己本身就不能再指向原来的下一结点了
// 否则会发生无限循环
head.next = null;
// 我们把每次反转后的结果传递给上一层
return cur;
}
}
