生命不是安排󿼌而是追求�生命的意义可能永远不会有答案，但也要感受这种没有答案的生活。

                                                                                                                    --弗吉尼亚.  伍尔芙        。
目录。

前言：

🌸1.复制带随机指针的链表。

🌅1.将结点链接复制到原链表每个结点的后面。

🍁2.将原结点的random索引到新结点的random上 。

🌺3.首先链接原链表，然后开始将复制的结点插入尾部，形成我们复制的链表。

4.完整代码。

---

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

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

返回复制链表的头节点。

用一个由 n 由节点组成的链表表示输入/输出中的链表。每个节点使用一个 [val, random_index] 表示：

val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点󿀌则为  null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。

示例 1：
 。

输入：head = [[7,null],[13，0]，[11，4]，[10，2]，[1，0]]。
输出：[[7,null],[13，0]，[11，4]，[10，2]，[1，0]]。
 。

示例 2：

输入：head = [1，1]，[2，1]]。输出：[1，1]，[2，1]]。

 。示例 3：

输入：head = [[3,null],[3，0]，[3，null]]。输出：[[3,null],[3，0]，[3，null]]。

做题链接：用随机指针复制链表 。

前言：

这个问题真的很难想。，当我第一次看到这个问题时，，我自己也很傻，想了十分钟，#xff0c;没有想法󿀌然后我直接去看Leetcode的官方问题，了解一些步骤，但是还是有一些细节我不明白。，因为Leeetcode的官方解题只是一般的解题方法，细节没有单独拿出来。，我想这也是为了防止遇到一点困难就看问题的人，但是，我们仍然需要思考󿀌澄清代码的真相。但是活着的人不能被尿窒息，所以我去了。B站搜索这个问题的问题解决方案。，然后在。大学生UP主账户。看到他解释了这个问题，真的很厉害󿀌一遍又一遍地理解󿀌非常详细。，这个博客的代码也是UP主，我把链接放在这里，你可以去看看需要什么。
【C语言 Leetcode 138题 复制带随机指针的链表]https://www.bilibili.com/video/BV1oP4y1T7XG?vd_source=6ade441273c0eb7b8c5862c1e54b71。

🌸1.复制带随机指针的链表。

我们先说。一般思路。，我们不是要复制这个带随机指针的链表吗？
   1.。我们可以先复制原链表的每个结点，复制的新结点具有原结点值，但是没有随机指针的方向，因为原点的随机指针也是随机的。然后我们将复制的新结点链接到原结点后面，然后把它们全部链接起来，形成两倍长的链表。效果图如下：：

  2. 。通过第一步󿀌我们大致有了复制链表的雏形，这一步就是把。原结点(。。。random。)随机指针。索引到。新节点(。。。random)随机指针。我们将在下面详细介绍细节。
 。3.。假设我们已经采取了第二步。原结点(。random。)随机指针。索引到。新结点(。。random)随机指针。
这一步是取下新结点到原结点，然后依次插上尾巴。新复制的链表，但是，我们不能改变原链表󿀌因此，我们还需要打原结点。红叉叉。链接的地方，最后，返回复制链表的头结点。

接下来是我们具体细节的展示。坐稳了，老铁，老司机准备出发。

🌅1.将结点链接复制到原链表每个结点的后面。

原始链表中有多少个节点，我们需要复制几个结点，很明显，我们通过循环实现，每一步循环，我们都需要一个新的malloc节点。，然后在复制的结点链接的原结点上。但是。这里的链接还有一个细节需要注意。

代码࿱直接访问此步骤a;

//1.将结点链接复制到原链表每个结点的背面    struct Node*cur=head;///cur指向头结点    while(cur)    {         struct Node*copynode=(struct Node*)malloc(sizeof(struct Node));//malloc新结点        copynode->val=cur->val;//复制值        copynode->next=cur->next;        cur->next=copynode;        cur=cur->next->next;///因为cur后面链接了一个新的结点，                            //所以我们必须让cur走两步才能到达下一个原点    }。

🍁2.将原结点的random索引到新结点的random上 。

🍁2.将原结点的random索引到新结点的random上 。这一步是最难的一步，如何将原结点的random索引到新结点的random上？很苦恼󿀌但让我们仔细观察一下。第一步是链接链表的外观。。

观察原结点随机指针的方向。

上代码：

//2.将原结点的random索引到新结点的random上 cur=head; while(cur) { struct Node*copynode=cur->next;///copynode复制的结点 if(cur->random==NULL) { copynode->random=NULL; } else { copynode->random=cur->random->next; } cur=cur->next->next;////这里的距离也是两倍 }。

🌺3.首先链接原链表，然后开始将复制的结点插入尾部，形成我们复制的链表。
假设我们已经链接了复制结点的随机指针，下一步是链接原来的结点，然后取下复制的结点，然后将其插入尾部。

假设我们已经链接了复制结点的随机指针，下一步是链接原来的结点，然后取下复制的结点，然后插入尾部。

这个代码实现起来比较简单。

//3.开始将复制的结点插入头部，我们复制的链表，然后链接原链表。    cur=head;    struct Node*copyhead=NULL;    struct Node*copytail=NULL;    while(cur)    {         struct Node*copynode=cur->next;        struct Node*next=copynode->next;        cur->next=next;        if(copytail==NULL)///第一次尾插，将复制的第一个结点直接给尾部和头部        {             copyhead=copytail=copynode;        }        else        {             copytail->next=copynode;//尾插            copytail=copytail->next;//更新尾        }        cur=next;    }    return copyhead;}。

4.完整代码。

struct Node* copyRandomList(struct Node* head) { //1.将结点链接复制到原链表每个结点的背面 struct Node*cur=head;///cur指向头结点 while(cur) { struct Node*copynode=(struct Node*)malloc(sizeof(struct Node));//malloc新结点 copynode->val=cur->val;//复制值 copynode->next=cur->next; cur->next=copynode; cur=cur->next->next;///cur后面链接了一个新的结点，所以我们必须让cur走两步才能到达下一个原点 } //2.将原始节点的random索引到新节点的random上 cur=head; while(cur) { struct Node*copynode=cur->next;///copynode复制的结点 if(cur->random==NULL) { copynode->random=NULL; } else { copynode->random=cur->random->next; } cur=cur->next->next;////这里的距离也是两倍 } //3.开始将复制的结点插入头部，我们复制的链表，然后链接原链表。 cur=head; struct Node*copyhead=NULL; struct Node*copytail=NULL; while(cur) { struct Node*copynode=cur->next; struct Node*next=copynode->next; cur->next=next; if(copytail==NULL)///第一次尾插，将复制的第一个结点直接给尾部和头部 { copyhead=copytail=copynode; } else { copytail->next=copynode;//尾插 copytail=copytail->next;//更新尾 } cur=next; } return copyhead;}。 。 。