LeetCode题目：K个一组翻转链表_给定一个包含 n 个元素的链表,现在要求每 k 个节点一组进行翻转

题目描述：

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
示例：
给你这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5
说明：
你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-nodes-in-k-group
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

在这个题目里面，需要将原来的链表分为K个K个一组，如果能分成一组的，就执行倒序函数，如果不够分成一组的，就直接输出原来的顺序。
首先需要设置一个pre和end变量，用于指向节点所在的位置，pre用于存放上次分组倒序之后的最后一个节点，end用于指向一个分组结束的位置。
循环体中，第一步就是确认end的位置，直接去到排序前，这个组中的最后一个节点，然后将这个节点的next存放起来，方便下一次循环使用；start就是上一次循环最后一个节点pre的next，然后将end.next设为空，用于倒序循环的结束条件；倒序执行完之后，start就是最后一个节点，前面倒序倒序后的最后一个节点pre的next指向倒序后的第一个节点，倒序操作就结束了。再将start设置为pre，然后end同样置于这个节点，方便下一个循环的执行，下次循环第一步就是改变end。
倒序函数中，首先设置一个pre为空，它将作为倒序之后最后一个节点的next，当前节点curr初始是输入的节点，记为head；循环的结束条件是curr为空，循环体执行：先把curr的next存放在起来，上一次操作的节点就是当前这个操作节点的next，然后将当前节点curr赋给pre，预先存放起来的原来节点的next就赋给curr，准备下一次的循环。

代码（Java）：

public class Solution {
	public static void main(String[] args) {
		ListNode head = new ListNode(1);
		head.next = new ListNode(2);
		head.next.next = new ListNode(3);
		head.next.next.next = new ListNode(4);
		head.next.next.next.next = new ListNode(5);
		reverseKGroup(head, 3);
	}
	
	public static ListNode reverseKGroup(ListNode head, int k ) {
		ListNode dummy = new ListNode(0);
		dummy.next = head;
		
		ListNode pre = dummy; //预设pre和end两个变量表示在链表中的位置
		ListNode end = dummy;
		
		while(end.next!=null) {
			for(int i = 0;i<k&&end!=null;i++) end = end.next; //分组，这个循环之后，end会是下一次循环的第一个节点
			ListNode start = pre.next;  //循环开始为节点
			ListNode next = end.next;   //记录下来下一个循环开始的节点
			end.next = null;	//为了给reverse函数的循环提供停止条件
			pre.next = reverse(start);  //在这个里面调整节点的顺序
			
			start.next = next;  //调完顺序后start是最后一个节点，下一个指向next
			pre = start;	//当前的start调整完顺序后是最后一个，是下一次循环的上一节点
			end = pre;		//将end和pre置于同一位置，下次循环是，end首先向前进，找到再下一次循环的起始节点
		}
		return dummy.next;
	}
	
	private static ListNode reverse(ListNode head) {
		ListNode pre = null;  //输入进来的是head，设定他的前一个节点是空的，空节点将会成为调完顺序后的最后一个节点的next
		
		ListNode curr = head;  //还没开始循环，当前节点就是输入的节点
		while(curr!=null) {
			ListNode next = curr.next;   //先把下一个要处理的节点保存起来
			curr.next = pre;		//当前节点的next，就是上一个处理过得节点
			pre = curr;  		//处理完了，当前节点就成了下次循环的上一节点
			curr = next;		//把预先保存起来的要下一次循环处理的节点赋给curr，表示下个循环开始处理他
		}
		return pre;		//全部处理完了，返回处理完后的第一个节点
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44