[力扣_25] K个一组翻转链表
题目入口：点击进入
相关算法：
- 分割链表——时间复杂度O(n*k)，空间复杂度O(1)
思路和算法：
本题的目标非常清晰易懂，不涉及复杂的算法，但是实现过程中需要考虑的细节比较多，容易写出冗长的代码，但是只需要对链表和指针能理解透彻的话，就很容易可以写出来
分割链表
我们需要将链表结点按照k个一组分组，所以可以使用一个指针依次指向每组的头结点，这个指针每次向前移动k步，直至链表结尾，对于每个分组，我们先判断它的长度是否大于或等于k。
接下来需要考虑的就是，如何反转分组内的一个链表，反转链表并不难，我使用的递归来反转。
同时需要考虑如何存储反转后的头，反转后的尾，反转的前置结点，这样才能将其链接起来。
我们维护一个全局遍历用于存储每次遍历后的头，也就是一组链表的尾端，逆转后，当前链表的头就会变成当前链表的尾，当前链表的尾就会变成当前链表的头，我们每次返回逆转后的头，然后就可以完成链接
图解如下：
- 链表分区为已翻转部分+待翻转部分+未翻转部分
- 每次翻转前，去遍历链表，给定一个计数遍历，走一次则递增1，直到等于k才进行反转
需记录翻转链表前驱和后继，方便翻转完成后把已翻转部分和未翻转部分连接起来
- 需要记录第一次反转的头，用于返回。
- 用递归逆置，每次维护一个全局遍历来存储逆置后的头结点，就是逆置前的尾结点，然后逐步返回当前结点，最后返回的就是逆置后的头结点
代码如下所示：
struct ListNode* H;//存储每次逆置完后的头
struct ListNode* InverseList(struct ListNode** L)//逆置链表
{
if ((*L)->next == NULL)
{
H = (*L);
return (*L);
}
else
{
struct ListNode* p = InverseList(&(*L)->next);
p->next = (*L);
p = p->next;
p->next = NULL;
return p;
}
}
struct ListNode* reverseKGroup(struct ListNode* head, int k){
int count = 0;//计数，由于不带头结点，则从1开始
struct ListNode* h1 = head;//临时头指针，用于每次存储段落头
struct ListNode* t1 = h1;// t1作用每次查找段落尾端，划定边界
struct ListNode* h2 = NULL, *tali=NULL, *tali2 = NULL;
//h2用于获取当前段的下一段头，方便下次递归，与H不同的是，它是原本的头，而H是逆置后的头
//tali为当前逆置后的尾
//tali保存上一次逆置后的尾
int sign = 0;//哨兵，确定是否第一次，在程序内初始化
while (t1 != NULL)//当尾端为空时，表示后续无结点或不满足k
{
t1 = h1;//用于查找尾端，初始化
count = 1;
while (count < k && t1 != NULL)
{
t1 = t1->next;//查找尾端
count++;
}
if (t1&&count == k)//当段落长度满足k时
{
h2 = t1->next;//标记下一段落的头
t1->next = NULL;//划定边界
tali = InverseList(&h1);//将此段落逆置，tali存储逆置后的尾
if (!sign)//第一次，记录整条链表的头，此语段只执行一次
{
head = H;
tali->next = h2;//连接下一段
sign = 1;//哨兵死亡
}
else
{
tali2->next = H;//将上一段尾与当前头相连接
tali->next = h2;//将当前尾与下一段头连接
}
}
tali2 = tali;//记录当前尾
h1 = h2;//更新头
}
return head;
}由于没有设置虚结点，我使用了一个哨兵来确定是否是第一次，保存第一次的头。
然后在第一次之后每次更新当前段落的尾端，也就是下一段落前端的前驱，第一次当然不用前驱相连
每次遍历当前段落的尾端时，记录尾端的下一个结点就是后继
简单来说，就是
- 反转前的前驱链接——反转后的头——反转后的尾——链接反转前的后继