题解 | #复杂链表的复制#

/*
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;
    }
};