没有关系的话,那就去建立关系吧

奋斗吧
奋斗吧
擅长邻域:未填写

标签: 没有关系的话,那就去建立关系吧

2023-03-20 03:00:11 230浏览

没有关系,就去创建关系。--链表好题分享

        今天给大家分享一道链表的好题--链表的深度拷贝,学会这道题,你的链表就可以达到优秀的水平了。力扣

         先来理解一下题目意思,即建立一个新的单向链表,里面每个结点的值与对应的原链表相同,并且random指针也要指向新链表中与原链表对应的那个相对位置。(即假设原链表中的第一个结点的random指向原链表的最后一个结点,那么新链表的第一个结点也要指向新链表的最后一个结点,即random指针是链表内部确定相对位置的一个指针)。

        首先,拷贝一个新的链表,其对应结点的值与原链表对应结点的值相同是很容易实现的。可以用一个cur指针遍历原链表,然后建立一个新链表头,然后逐个尾插既可。   


    struct Node* cur=head;
    struct Node* newhead = NULL;
    struct Node* tail = NULL;

    while(cur)
    {
        //每次尾插都需要一个新结点,其val与原链表对应相等
        struct Node* newnode = (struct Node*)malloc(sizeof(struct Node));

        //第一次尾插时
        if(NULL ==tail)
        {
            newhead = tail =newnode;
            newnode->val = cur->val;
            newnode->next = newnode->random = NULL;
                
        }
        //后续尾插
        else
        {
            tail->next = newnode;
            tail = tail->next;
        }
        //拷贝一个新结点后,cur往后走
        cur = ucr->next;
    }

此时,只是完成了next链接和val拷贝,random的指向还没有拷贝。

暴力求解O(N^2)

可以建立一个结构体的指针数组   struct Node* arr[n]  n为原链表中的结点数

    struct Node* arr[n];
    int count = 0;
    while(cur)
    {
        arr[count] = cur->random;
        count++;
        cur =cur->next;
    }

再次利用cur遍历原链表,将每个结点的random保存在创建的结构体指针数组 arr中。

struct Node* newcur=newhead;
    int newcount=-1;
    while(newcur)
    {
        ++newcount;//每次进来都拿到原链表的一个random
        struct Node* tmp = arr[newcount];//用tmp保存这个random
        cur = head;
        while(cur != tmp)
        {
            //遍历原链表,看看此时的random是原链表的第几个结点
            count++;
        }

        //找到新链表中对应的第count个结点
        struct Node* find = newhead;
        while(count--)
        {
            //一共走count步
            newhead = newhead->next;
        }
        //找到了newcur位置的random的指向
        newcur->random = find;
        //newcur继续往后走
        newcur = newcur->next;

    }

暴力解法虽然也能解决问题,但是时间复杂度为O(N^2),效率低,不推荐。

更优解O(N)

        通过暴力解法我们可以发现,寻找random指向的难点在于它是随机的,如果想要确定具体的相对位置(相对于头是第几个)则必须经过2次遍历,那么怎样简化寻找相对位置的过程呢?

        想一下random的关系在哪里出现,应该只有原链表中,而我们又想要建立新链表中random的关系,因此我们必须建立原链表与新链表直接的关系,通过原链表的random找到新链表的random。

        再借助next指针思考,我们可以将新链表对应的结点连接到原链表上。

        

 此时逻辑一下子清晰了,每个新结点都在原对应结点的next位置。

例如:对于13这个结点的random连接,新13->random = 原13->random->next,即通过原链表random的查找方式,再加上next,来连接新链表的random。

具体的实现过程分为3个方面。

1、连接原、新链表


    struct Node* cur=head;
    while(cur)
    {
        //建立新结点并初始化
        struct Node* newnode = (struct Node*)malloc(sizeof(struct Node));
        newnode->next = newnode->random =NULL;
        random->val = cur->val;

        //先保存一下原结点的下一个结点
        struct Node* next = cur->next;
        //将新结点连接到原链表
        cur->next = newnode;
        newnode->next = next;
        //cur继续往后走
        cur = next;

    }

2、建立新链表的random联系

    cur = head;
    while(cur)
    {
        //确保cur不为NULL,再建立copy指向cur的next
        struct Node* copy = cur->next;
        
        //建立copy的random联系时,要确保其不为空,否则不能进行next操作
        //因此这里讨论一下原链表的random是否为空
        if(NULL == cur->random)
        {
            copy->random = NULL;
        }
        else
        {   
            copy-> random = cur->random->next;
        }

        //连接后cur继续往后走
        cur = copy->next;
        
    }

要注意,copy指针和cur指针移动的位置,可以理解为cur不为空时,建立copy指向此时cur的下一个,完成相关连接后copy丢弃,cur往后走,copy只起到临时变量的作用(连接后便丢弃)。

 

3、分离原、新链表

分离的过程直接将copy部分的结点尾插到一个新结点即可

struct Node* newhead=NULL,*tail=NULL;
    cur=head;
    while(cur)
    {
        struct Node* copy = cur->next;
        struct Node* next = copy->next;

        if(NULL == tail)//第一次尾插
        {
            newhead = tail =copy;
        }
        else//后续尾插
        {
            tail->next = copy;
            //tail往后走,指向新的最后一个结点
            tail = tail->next;
        }
     
        //分离原链表,cur继续往后走
        cur->next=next;
        cur= next;

    }

     return newhead;

这部分要注意,else内部tail往下走是后续尾插才有的操作。

 

总结:为了优化代码,使时间复杂度变为O(N),必须建立原来链表的新链表直接的联系,借助原链表的random->next,来连接新链表的random。

所以说,没有关系的话,那就去勇敢的建立关系吧。

 

好博客就要一起分享哦!分享海报

此处可发布评论

评论(0展开评论

暂无评论,快来写一下吧

展开评论

您可能感兴趣的博客

客服QQ 1913284695