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
作为传入参数。
按照这个思路,将所有的拷贝结点的random连接起来:
逐一将拷贝结点尾插到新链表的同时恢复原链表的链接关系,最后返回newhead即可
综上,该题完整解题代码如下:
struct Node* BuyNode(int x)
{
struct Node* newnode = (struct Node*)malloc(sizeof(struct Node));
if (newnode == NULL)
{
perror("malloc fail::");
return NULL;
}
newnode->val = x;
newnode->next = NULL;
newnode->random=NULL;
return newnode;
}
struct Node* copyRandomList(struct Node* head)
{
//1.逐一拷贝链表结点并将其链接在原结点的后面
struct Node*cur=head;
while(cur)
{
int data=cur->val;
struct Node*new=BuyNode(data);
new->next=cur->next;
cur->next=new;
cur=cur->next->next;
}
//2.拷贝结点的random,把原结点后面的拷贝结点的random和原结点random的后一个结点拷贝起来.
cur=head;
while(cur)
{
if(cur->random!=NULL)
{
cur->next->random=cur->random->next;
}
else
{
cur->next->random=cur->random;
}
cur=cur->next->next;
}
//3.将拷贝结点摘下尾插到新链表中,同时恢复原链表.
cur=head;
struct Node*newhead=NULL;
struct Node*tail=newhead;//记录新表尾
while(cur)
{
//先把新结点给新链表
if(newhead==NULL)
{
newhead=cur->next;
tail=newhead;
}
else
{
tail->next=cur->next;
tail=tail->next;
}
//再改变老节点的关系
cur->next=tail->next;
cur=cur->next;
}
if(tail!=NULL)//防止空指针解引用
{
tail->next=NULL;
}
return newhead;
}
提交运行:
这是一道经典的链表面试题目,其中不仅仅是考察我们对题目的思路,同样也需要我们有很扎实的链表插入,删除,链接等操作的基本功.如果可以很轻松的完成这道题,那么恭喜你,你的链表已经达到了可以出师的水平,请继续向着星辰大海进发吧!