清晰易懂的“K个一组翻转链表”解法_链表 14,13,12,11,10,9,8,7,6,5,4,3,2,1 从1开始倒着k个一组翻转 结

题目来源：Leetcode K个一组翻转链表

一.题目

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

示例：

给你这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5
1
2
3

说明：

• 你的算法只能使用常数的额外空间。
• 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

二.解题核心思路

要想解决该问题需要解决如下几个问题：

• 寻找到K个一组结点（存在时）；
• 如何能够将当前一组逆序后连接到之前“逆序处理”好的序列后面，以及将当前一组逆序结点的末尾连接未经处理的链表结点序列。

2.1.如何寻找K个一组结点

• 可采用双指针法，这里利用两个指针pre和p，其中pre用来指向K个结点的开头，p用来指向K个结点的末尾。
• 开始时pre和p同时指向同一个结点，然后移动p到第k个结点处，若在移动过程中结点p为变为空则说明剩余的结点数少于K个，此时说明原链表已经处理完毕。

伪代码

pre = p = start_position //start_position开始寻找K个一组节点的第一个结点位置
for i = 1 to k
	p = p->next;
	if p is NULL
		break
1
2
3
4
5

2.2.逆序连接

2.2.1.处理步骤

在介绍之前首先说明一些使用到的指针（pre和p上面已经介绍）：

• curhead：指向已经经过处理的部分序列的末尾；
• rear：用来保存p指针之后的序列，防止其丢失；
• curp：用来暂时指向从k个一组结点中取出来的结点；

设之前已经翻转了几组数据，此时curhead执行在处理完的序列的末尾：

1. 首先需要将curhead的next指针置为NULL，即断可处理完的序列和未处理完的序列之间的连接。
2. 同时使用rear指针指向p指向的后一个结点。
3. 然后逐一的将从pre到p的全部结点取下来，取下的结点用curp指向，然后插入到curhead结点相邻的下一个位置。（插入的方法curp->next = curhead->next; curhead->next = curp）
4. 通过步骤三的操作就可以完成将pre到p的结点序列逆序连接，然后curhead要移动到新处理完的序列的末尾结点位置，然后将rear指向的剩下的序列连接在其后面。

2.2.2.逆序连接算法图示

设K = 3，原始元素列表为1->2->3->4->5->6->7，则经过一次处理后的链表如下图所示

第二次处理第一步：将处理好的序列与未处理的序列断开,并将p的后一结点用rear指向

第二次处理第二步：从K个一组序列取出第一个结点，连接到与curhead相邻的下一位置

第二次处理第三步：取出第二个结点，连接到curhead相邻的下一位置

第二次处理第四步：取出最后一个结点，连接到curhead相邻的下一位置

第二次处理第五步：将curhead指针移动至当前已处理序列的末尾，并将未处理的指针序列连接在其后，然后重新初始化pre和p进行下一次处理

三.核心代码(C语言)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 
struct ListNode* reverseKGroup(struct ListNode* head, int k) {
	 struct ListNode* pre, * p;
	 struct ListNode *rear, * curhead,*curp;
	 int i;

	 curhead = (struct ListNode*)malloc(sizeof(struct ListNode));
	 pre = p = head;
	 while (p)
	 {
		 for (i = 1; i < k; i++)
		 {
			 if (!p)
				 break;
			 p = p->next;
		 }
		 if (p)
		 {
			 rear = p->next;
			 curhead->next = NULL;
			 if (pre == head)
				 head = curhead;
			 while (pre != rear)
			 {
				 curp = pre;
				 pre = pre->next;
				 curp->next = curhead->next;
				 curhead->next = curp;
			 }
			 while (curhead->next)
			 {
				 curhead = curhead->next;
			 }
			 curhead->next = rear;
			 p = pre;
		 }

	 }
	 return head->next;
 }
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
45
46
47