编号0016 复制带随机指针的链表
给你一个长度为 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）
链接：https://leetcode.cn/problems/copy-list-with-random-pointer
讲真的 看到这个题目的第一眼 头疼！
咋有这么多字捏 完全不想看
但是没办法啊 硬着头皮读吧
我用三句话把这个题目解释下
1 有一个链表 链表的节点有三个结构组成 两个指针 一个值
2 两个指针一个指向下一个节点 一个指向一个随机节点
3 我们要拷贝一份这个链表 但是不能改变它的结构
好的 读完了 下机！
才怪 开始想思路
还是一样 我们先看图
往后找的倒是简单 只要记住它们的相对位置 然后往后面走x步就可以了
但是往前的呢？
还是要记住它们的相对位置然后从前往后开始遍历= =
woc 这时间复杂度不直接上O（N*N）了
想想就不想写了 下机！
顺手去翻翻评论区
这里就发现了一种很巧妙的解法
我们先照抄题目给我们的链表写出一个类似的链表出来 （值全部传递）
之后我们将这个单链表插入到题目给我们的链表的下一位去
这样子我们看看 如果是找随机值的话
13的随机值是指向7的
想要找到7我们只需要找到它的下一个位置就可以了！ 妙啊！
但是这里有个特殊情况哈
如果随机值是指向NULL的 我们直接赋值NULL就可以了！
也就是加一行代码的事
我们先来看看细节怎么样
首先我们先来复制这个链表除了随机值以外的其他部分
// 先创建一个新链表 新链表除了随机值之外一切都相同 struct Node* newhead = NULL; struct Node* newtail = NULL; struct Node* cur = head; while(cur) { if(newhead==NULL) { newhead=newtail=BUYSList(); newhead->val = cur->val; } else { newtail->next=BUYSList(); newtail=newtail->next; newtail->val = cur->val; } cur=cur->next; } newtail->next=NULL;
这样子我们就完成了一个单链表的简单拷贝（无随机值）
现在我们执行插入操作
我们这里使用cur遍历 下面的链表
使用next记录下面的下一位
使用newcur遍历 上面的链表
使用newnext继续下面链表的下一位
上代码
//按照我们的方式链接两个链表 cur = head; struct Node* next = head; struct Node* newcur = newhead; struct Node* newnext = newhead; while(cur) //画图判断下是否cur指向空指针的时候结束 { // next都往前进一 next=next->next; newnext=newnext->next; //开始链接 cur->next = newcur; newcur->next = next; //迭代 cur = next; newcur = newnext; }
接下来我们就可以开始遍历整个链表赋值随机值了
赋值方式如下图
//准备工作完毕 开始赋值随机值 cur = head; next = head; while(cur) { next=cur; next=next->next; if(cur->random==NULL) { next->random=NULL; } else { next->random = cur->random->next; } cur = next->next; }
**这里要注意的一点是 我们要找清楚需要赋随机值的位置 **
全部赋完随机值之后我们就可以开始将这两个链表解开了
画图表示如下
代码表示如下
// 分开两个链表 cur = head; next = head; while(cur->next) { // next往前走 next=next->next; //cur链接原来链表的位置 cur ->next = next->next; // 迭代 cur = next; }
以上我们就完成啦
我们来试试看能不能通过
过啦
那么这就是本题的时间复杂度0（N）的解法啦
所有代码表示如下
/** * Definition for a Node. * struct Node { * int val; * struct Node *next; * struct Node *random; * }; */ struct Node* BUYSList(void) { struct Node* newnode =(struct Node*)malloc(sizeof(struct Node)); return newnode; } struct Node* copyRandomList(struct Node* head) { if(head==NULL) { return NULL; } // 先创建一个新链表 新链表除了随机值之外一切都相同 struct Node* newhead = NULL; struct Node* newtail = NULL; struct Node* cur = head; while(cur) { if(newhead==NULL) { newhead=newtail=BUYSList(); newhead->val = cur->val; } else { newtail->next=BUYSList(); newtail=newtail->next; newtail->val = cur->val; } cur=cur->next; } newtail->next=NULL; //按照我们的方式链接两个链表 cur = head; struct Node* next = head; struct Node* newcur = newhead; struct Node* newnext = newhead; while(cur) //画图判断下是否cur指向空指针的时候结束 { // next都往前进一 next=next->next; newnext=newnext->next; //开始链接 cur->next = newcur; newcur->next = next; //迭代 cur = next; newcur = newnext; } //准备工作完毕 开始赋值随机值 cur = head; next = head; while(cur) { next=cur; next=next->next; if(cur->random==NULL) { next->random=NULL; } else { next->random = cur->random->next; } cur = next->next; } // 分开两个链表 cur = head; next = head; while(cur->next) { // next往前走 next=next->next; //cur链接原来链表的位置 cur ->next = next->next; // 迭代 cur = next; } return newhead; }
