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

思路：先沿着next指针把有序部分拷贝下来，然后每个结点分别拷贝random部分。建立一个map，每次拷贝的时候，从原来部分读取一个地址，就去map查找对应新链表的地址是什么。要充分利用next有序这一条件。

class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead) {
        RandomListNode *newHead=nullptr,*p0=nullptr,*p1=nullptr,*newP=nullptr,*r0=nullptr,*r1=nullptr;
        map<RandomListNode*,RandomListNode*> locMap;//用来查找旧链表里面的地址对应新链表的什么地址
        for(p0=pHead;p0!=nullptr;p0=p0->next){
            newP=new RandomListNode(p0->label);
            locMap[p0]=newP;//存入map
            if(newHead==nullptr){
                newHead=newP;//newHead是新链表的头
                p1=newP;//p1是新链表的尾，下面每次操作要取p1=p1->next
            }
            else{
                p1->next=newP;
                p1=p1->next;
            }
        }
        p1=newHead;
        p0=pHead;
        while(p0!=nullptr){
            r0=p0->random;//这部分开始复制random
            r1=locMap[r0];//查表
            p1->random=r1;
            p0=p0->next;
            p1=p1->next;
        }
        return newHead;
    }
};