前言

😂这方法太棒了！

一、复杂带随机指针链表题链接

题目描述

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。

深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

测试样例1：

测试样例2：自己指向直接

测试样例3：val全相同

测试样例4：为空

题目思路

1. 对于链表，最好的方法就是开辟空间
2. 除了空，其他节点都另外开辟一个空间，来重新连接这个链表
   
3. 然后通过原链表节点的random的指向来连接新开辟中random的关系
   
   4.最后来连接 开辟的新节点，重新连接老链表

注意：头节点为空的时候

代码如下：

struct Node* copyRandomList(struct Node* head) 
{

    if(head==NULL)
    return NULL;

	//开辟空间
    struct Node*copy=NULL;
    struct Node*cur=head;
    while(cur)
    {
        struct Node*next=cur->next;
        copy=(struct Node*)malloc(sizeof(struct Node));
        copy->val = cur->val;
        copy->next=next;
        cur->next=copy;
        cur=next;
    }
    cur=head;
    copy=cur->next;
    while(cur)
    {
        copy=cur->next;
        if(cur->random!=NULL)
        {
            copy->random=cur->random->next;
        }  
        else
        {
            copy->random=cur->random;
        }
        cur=copy->next;
    }
    //链接random
    struct Node*guardHead=NULL;
    struct Node*guardTail=NULL;
    struct Node*liberate=NULL;
    guardTail=guardHead=liberate=(struct Node*)malloc(sizeof(struct Node));
    cur=head;
    while(cur)
    {
        copy=cur->next;

        cur->next=copy->next;

        guardTail->next=copy;

        guardTail=copy;

        cur=copy->next;

    }
    guardHead=guardHead->next;
    free(liberate);
    return guardHead;

}

总结

🤣就是玩！