🍍图案大全题目链接：138. 复制带随机指针的链表
🍈题目描述：
给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 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 作为传入参数。
来源：力扣（LeetCode）
🍈思路一：
🍉 代码：
struct Node* copyRandomList(struct Node* head) { //哨兵位头节点 struct Node*phead=(struct Node*)malloc(sizeof(struct Node)); struct Node*ptail=phead; struct Node*cur=head; //创建复制链表 while(cur) { struct Node*new=(struct Node*)malloc(sizeof(struct Node)); new->val=cur->val; ptail->next=new; ptail=new; cur=cur->next; } ptail->next=NULL; cur=head; struct Node*curcopy=phead->next; while(curcopy) { //如果随机结点不是空，通过比较地址，用count记录相对第一个节点的位置 if(cur->random) { int count=0; struct Node*findrandom=head; struct Node*findnode=phead->next; while(findrandom!=cur->random) { count++; findrandom=findrandom->next; } while(count--) { findnode=findnode->next; } curcopy->random=findnode; } //原链表随机结点为空，那么复杂链表的随机结点也为空 else { curcopy->random=NULL; } cur=cur->next; curcopy=curcopy->next; } struct Node*pp=phead->next; free(phead); return pp; }
🍋提交结果：
🍒思路二：
🥝代码：
struct Node* copyRandomList(struct Node* head) { //如果原链表就是空，直接返回NULL if (head == NULL) { return NULL; } struct Node* Next = head->next; //断开连接时，找不到下一个结点，提前保留 struct Node* prev = head; while (prev) { //创建结点并连接 struct Node* newnode = (struct Node*)malloc(sizeof(struct Node)); newnode->next = NULL; newnode->random = NULL; prev->next = newnode; newnode->next = Next; //迭代 prev = Next; if (Next) { Next = Next->next; } } prev = head; struct Node* new = head->next; while (prev) { //新节点连接 new->val = prev->val; //拷贝val //如果原链表的random不是指向NULL，那么复制链表的random就是原链表的random指向的下一个。 if (prev->random) { new->random = prev->random->next; } else//如果原链表的random是指向NULL,那么复制链表的random也指向NULL { new->random = NULL; } //迭代 if (new->next) { new = new->next->next; } prev = prev->next->next; } //将复制链表从原链表中拆开 struct Node* phead = (struct Node*)malloc(sizeof(struct Node)); struct Node* ptail = phead; struct Node* cur = head->next; while (cur) { ptail->next = cur; ptail = cur; if (cur->next) { cur = cur->next->next; } else { cur = cur->next; } } //返回 return phead->next; }
🍇测试结果：
🍆最后:
你若想得到这世界最好的东西，先得让世界看到最好的你。
