前言: 。

💥🎈个人主页:Dream_Chaser～ 🎈💥

✨✨刷题专栏:http://t.csdn.cn/UlvTc。

⛳⛳本文内容:扣链表OJ题目。

目录。

letcode138. 用随机指针复制链表。

1. 问题描述。

二、代码思路：。

2.1将复制节点插入原节点后面。

2.2控制复制节点的random    。

2.3复制节点解决后尾插入构成复制链表，恢复原链表。

letcode138. 用随机指针复制链表。

来源:138. 复制带有随机指针的链表 - 扣除（LeetCode）

1. 问题描述。

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

这个链表的结构 。深拷贝。。 深度拷贝应该恰到好处 。n。 。个 。全新。 节点组成󿀌每个新节点的值都设置为其对应的原节点值。新节点的 。next。 指针和 。random。 指针还应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。链表中的指针没有复制。

原链表中的节点应指向 。。

例如，假如原链表中有 。X。 和 。Y。 。两个节点，其中。 。X.random --> Y。 。。然后复制链表中对应的两个节点。 。x。 和 。y。 ，同样有。 。x.random --> y。 。

返回复制链表的头节点。

题解接口: 。

struct Node* copyRandomList(struct Node* head) {     }。

二、代码思路：。

2.1将复制节点插入原节点后面。

        复制节点：遍历原链表，每个节点�创建副本节点，并将其插入原节点后面。

我们一步一步地进行分解。，首先，malloc是一个新的节点，然后让copy指针接收#xff0c;将原链表第一节点的val值赋值给新malloc的链表。

        最后，记得cur=next，让cur指向next，循环条件是cur不是null，回到循环󿀌重复。①②③④⑤⑥⑦。的步骤。

        这是链表的最后一种情况。 。

2.2控制复制节点的random    。

• 设置。random。指针：遍历链表󿀌每个原节点�设置相应的副本节点。random。指针。

1. 假如原节点。random。指针为。NULL。，节点的副本。random。指针也设置为。NULL。；
2. 否则，副本节点。random。将指针设置为原节点。random。指针指向节点的副本节点。

#xff1分解动作a;

①把。cur。指针重新指向原链表头节点(。head。) 。

②进入。while。循环，条件是。cur。不为。NULL。,定义一个新指针。copy。然后让它指向新组成的链表头节点的下一个节点。cur->next 。     。

③     假如原链表。random。域指向的地址是。NULL。，然后指向新节点的random域。NULL。，

         假如原链表。random。域指向的地址不是。NULL。，此时此时此刻将是currr->random->next地址赋值新节点。copy->random。

④将。copy->next。赋值给。cur。

循环①②③④步骤，结束条件是cur指向NULL。

这是最后的情况.。

2.3将复制节点解开，尾插组成复制链表，恢复原链表。

        分离链表：合并后的链表，将链表分开。原链表。和。副本链表。。同时，恢复原链表。next。指针，使其指向原链表的下一个节点；同时，构建。副本链表。，通过。将副本节点依次添加到副本链表的末尾。

尾插:。

恢复链表。

         循环条件仍然是cur不是NUL，当cur指向NULL时，循环结束后直接返回副本链表的头节点。copyHead。

实现代码：。

struct Node* copyRandomList(struct Node* head) {     //1.将复制节点插入原节点后面    struct Node* cur=head;    while(cur)    {     struct Node* copy=(struct Node*)malloc(sizeof(struct Node));    copy->val=cur->val;    struct Node* next= cur->next;    //插入    cur->next=copy;    copy->next=next;    cur=next;     }    //2.控制复制节点的random    cur=head;    while(cur)    {         struct Node* copy=cur->next;        if(cur->random == NULL)        {             copy->random=NULL;        }        else        {             copy->random=cur->random->next;        }        cur= copy->next;    }     // 3、解开复制节点的尾插，形成复制链表，恢复原链表    struct Node*copyHead =NULL,*copyTail=NULL;    cur=head;    while(cur)    {         struct Node* copy=cur->next;        struct Node* next=copy->next;        //尾插        if(copyTail == NULL)        {             copyHead= copyTail=copy;        }    else    {         copyTail->next=copy;        copyTail=copyTail->next;    }    //恢复原链表   cur->next=next;    cur= next;    }    return copyHead;}。

执行:。

执行:。