LeetCode刷题--复制带随机指针的链表

1.题目

题目链接: https://leetcode.cn/problems/copy-list-with-random-pointer/

给你一个长度为 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 作为传入参数。

2.解题思路

我们分3个步骤来解决这个题目：

1.复制结点，插入到原结点和下一个结点之间；

2.根据原结点的random，处理复制结点的random；

3.把拷贝的结点解下来存放到新的链表中，恢复原链表的链接关系。

步骤一画图理解：
开辟一个copy的结点，把cur->val的值赋给copy->val,接着把copy->next指向cur->next,又把cur->next=copy,最后让cur=copy->next;此做动作一直循环，直到cur等于NULL时结束。

步骤二：
让copy指向cur的下一个结点,如果cur->randomNULL，则copy->randomNULL，否则copy->random=cur->random->next ，最后cur=copy->next；此动作一直循环，直到cur==NULL时结束。

第一个原结点的random指向的是NULL，所以拷贝结点的random也是指向的NULL；
第二个原结点的random指向的是7，所以拷贝结点的random也是指向的7，这里的7是拷贝结点的7；
这里copy->random=cur->random->next不太好理解，就是拷贝结点的random是指向原结点的random的next,这样才能指向7这个拷贝的结点。

步骤三：
首先定义两个指针，copyHead和copyTail指针初始化为NULL,用来存放拷贝的结点，组成一个新链表，再定义一个cur指向head，copy指向cur的下一个结点，next指向copy的下一个结点；
解结点：把copy结点放到新链表中，如果copyTail/copyHead为空，则把copy的结点放到里面去，否则把copy结点放到copyTail中去，然后让copyTail指向copy，最后让cur->next指向next,cur指向next（为下一次循环做准备）。

把拷贝的结点解下来的同时需要把原链表的链接关系重新链接好。

这样就算是把原链表深拷贝了。

3.完整代码

struct Node* copyRandomList(struct Node* head) {//复制结点，插入到原结点和下一个结点之间struct Node* cur =head;while(cur){struct Node* copy = (struct Node*)malloc(sizeof(struct Node));copy->val = cur->val;copy->next = cur->next;cur->next = copy;cur = copy->next;}//根据原结点的random，处理复制结点的randomcur = head;while(cur) {struct Node* copy = cur->next;if(cur->random == NULL){copy->random = NULL;}else{copy->random = cur->random->next;}cur = copy->next;}//把拷贝的结点解下来存放到新的链表中，恢复原链表的链接关系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 = copy;}//为下一次循环做准备cur->next = next;cur = next;}return copyHead;
}

不管你认为这篇文章写的好不好，反正没人点赞👍