给你一个长度为 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
作为传入参数。
提示:
0 <= n <= 1000
-104 <= Node.val <= 104
Node.random
为 null
或指向链表中的节点。我们可以将链表的每一个节点拆分为两个节点,即在原来的两个节点之间插入一个新的节点,这个节点是前一个节点的拷贝,例如对于链表 A→B→C,我们可以将其拆分为A→A′→B→B′→C→C′。先将拷贝节点连接在原链表中两个节点之间,然后依次对拷贝节点的random赋值,最后将拷贝节点拆分下来,得到新链表。
代码实现
/**
* Definition for a Node.
* struct Node {
* int val;
* struct Node *next;
* struct Node *random;
* };
*/
typedef struct Node Node;
struct Node* copyRandomList(struct Node* head) {
if(head==NULL)
return NULL;
//拷贝
Node* cur=head;
while(cur)
{
Node* copy=(Node*)malloc(sizeof(Node));
Node* next=cur->next;
copy->val=cur->val;
cur->next=copy;
copy->next=next;
cur=next;
}
//连接random
cur=head;
while(cur)
{
Node* copy=cur->next;
Node*next=cur->next->next;
if(cur->random==NULL)
{
copy->random=NULL;
}
else
{
copy->random=cur->random->next;
}
cur=next;
}
//分割
cur=head;
Node* newhead=NULL;
Node*tail=NULL;
while(cur)
{
Node* next=cur->next->next;
if(cur==head)
{
newhead=tail=cur->next;
}
else
{
tail->next=cur->next;
tail=tail->next;
}
cur->next=next;
cur=next;
}
return newhead;
}