[力扣_25] K个一组翻转链表

题目入口:点击进入

相关算法:

  • 分割链表——时间复杂度O(n*k),空间复杂度O(1)

思路和算法:

本题的目标非常清晰易懂,不涉及复杂的算法,但是实现过程中需要考虑的细节比较多,容易写出冗长的代码,但是只需要对链表和指针能理解透彻的话,就很容易可以写出来

分割链表

我们需要将链表结点按照k个一组分组,所以可以使用一个指针依次指向每组的头结点,这个指针每次向前移动k步,直至链表结尾,对于每个分组,我们先判断它的长度是否大于或等于k。

接下来需要考虑的就是,如何反转分组内的一个链表,反转链表并不难,我使用的递归来反转。

同时需要考虑如何存储反转后的头,反转后的尾,反转的前置结点,这样才能将其链接起来。

我们维护一个全局遍历用于存储每次遍历后的头,也就是一组链表的尾端,逆转后,当前链表的头就会变成当前链表的尾,当前链表的尾就会变成当前链表的头,我们每次返回逆转后的头,然后就可以完成链接

图解如下:

img

img

img

img

img

img

img

img

img

img

img

img

img

img

img

img

img

img

img

  • 链表分区为已翻转部分+待翻转部分+未翻转部分
  • 每次翻转前,去遍历链表,给定一个计数遍历,走一次则递增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;
}

由于没有设置虚结点,我使用了一个哨兵来确定是否是第一次,保存第一次的头。

然后在第一次之后每次更新当前段落的尾端,也就是下一段落前端的前驱,第一次当然不用前驱相连

每次遍历当前段落的尾端时,记录尾端的下一个结点就是后继

简单来说,就是

  • 反转前的前驱链接——反转后的头——反转后的尾——链接反转前的后继

本文链接:

https://nullcode.fun/72.html
1 + 6 =
快来做第一个评论的人吧~