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

首先我们在 每个节点的后面 复制一个节点，复制的就是当前节点的下一个节点，这样除 头结点外，每个节点都有了一个复制，然后就是修改 random指针，只要让每一个节点的 random 指针的指向，都指向现在节点 的下一个就可以了！就是p->next->random=p->random->next
下一步再分离出这个链表就可以了

/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead) {
        //复制新节点
        RandomListNode* cur=pHead;
        while(cur!=nullptr)
        {
            RandomListNode* ncur=new RandomListNode(cur->label);
            RandomListNode* next=cur->next;

            cur->next=ncur;
            ncur->next=next;
            cur=next;
        }

        //复制random指针
        cur=pHead;
        while(cur!=nullptr)
        {
            if(cur->random!=nullptr)
            {
                cur->next->random=cur->random->next;
            }

            cur=cur->next->next;
        }

        //分离得到复制的链表
        RandomListNode* dummy=new RandomListNode(-1);
        RandomListNode* newCur=dummy;
        cur=pHead;
        while(cur!=nullptr)
        {
            newCur->next=cur->next;
            newCur=newCur->next;

            //恢复原来的链表
            cur->next=cur->next->next;
            //更新到下一个结点
            cur=cur->next;
        }

        return dummy->next;
    }
};