/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;
Node(int _val) {
val = _val;
next = NULL;
random = NULL;
}
};
*/
class Solution {
public:
Node* copyRandomList(Node* head) {
if(!head) return NULL;
for(auto p=head;p;p=p->next->next)//复制小弟
{
auto t=new Node(p->val);
t->next=p->next;
p->next=t;
}
for(auto p=head;p;p=p->next->next)//复制random
if(p->random)
p->next->random=p->random->next;
//抽出链表
auto dummy=new Node(-1),tail=dummy;
for(auto p=head;p;p=p->next)
{
//将小弟节点插入新链表
auto new_node=p->next;
tail=tail->next=new_node;
//将原链表恢复
p->next=p->next->next;
}
return dummy->next;
}
};
138. 复制带随机指针的链表
发布时间 2023-04-04 15:18:06作者: 穿过雾的阴霾