[力扣_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;
}
由于没有设置虚结点,我使用了一个哨兵来确定是否是第一次,保存第一次的头。
然后在第一次之后每次更新当前段落的尾端,也就是下一段落前端的前驱,第一次当然不用前驱相连
每次遍历当前段落的尾端时,记录尾端的下一个结点就是后继
简单来说,就是
- 反转前的前驱链接——反转后的头——反转后的尾——链接反转前的后继