/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
class Solution {
private:
    RandomListNode* push_back(RandomListNode* pre,RandomListNode* cur){
        RandomListNode* node=new RandomListNode(cur->label);
        pre->next=node;
        return node;
    }
public:
    RandomListNode* Clone(RandomListNode* pHead)
    {
        RandomListNode* cur=pHead;
        RandomListNode* head=new RandomListNode(0);
        RandomListNode* node=head;
        unordered_map<RandomListNode*,RandomListNode*> record;
        while(cur){
            node=push_back(node,cur);
            record[cur]=cur->random;
            cur=cur->next;
        }
        cur=head->next;
        while(cur){
            RandomListNode* tmp=head->next;
            if(record.find(cur)!=record.end()){
                while(tmp){
                    if(tmp==record[cur]){
                        tmp->random=cur->random;
                    }
                    tmp=tmp->next;
                }
            }
            cur=cur->next;
        }
        return head->next;
    }
};