题解 | #复杂链表的复制#
复杂链表的复制
https://www.nowcoder.com/practice/f836b2c43afc4b35ad6adc41ec941dba
/*
struct RandomListNode {
int label;
struct RandomListNode *next, *random;
RandomListNode(int x) :
label(x), next(NULL), random(NULL) {
}
};
*/
class Solution {
public:
RandomListNode* Clone(RandomListNode* pHead) {
if(pHead==nullptr) return NULL;
//在原节点后面添加一个拷贝节点
RandomListNode* node=pHead;
RandomListNode* copynode=nullptr;
RandomListNode* tmp=nullptr;
while(node){
tmp=node;
node=node->next;
copynode=new RandomListNode(tmp->label);
tmp->next=copynode;
copynode->next=node;
}
//如果原节点random指针不为空，那么它的拷贝节点random指针就指向原来节点random指向的下一个
node=pHead;
while(node){
copynode=node->next;
if(node->random){
copynode->random=node->random->next;
}
node=node->next->next;
}
//将原节点和拷贝节点断开
node=pHead;
copynode=node->next;
tmp=copynode;
while(copynode->next){
node->next=copynode->next;//原节点下一个指向拷贝节点的下一个
node=node->next;//下一个原节点
copynode->next=node->next;//拷贝节点的下一个指向原节点的下一个
copynode=copynode->next;//下一个拷贝节点
}
//最后一个原节点下一个原来指向最后一个拷贝节点，现在要还原为指向空
node->next=nullptr;
return tmp;
}
};
