刷爆leetcode第五期 0016
编号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;
}