A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

 

class Solution {public:    RandomListNode *copyRandomList(RandomListNode *head) {        if(head==NULL) return head;        map
     
       hash;        map
      
        copyHash;        RandomListNode* copyHead=new RandomListNode(head->label);        RandomListNode* p=head;        RandomListNode* q=copyHead;        int index=0;        hash[p]=index;        copyHash[index]=q;        ++index;        p=p->next;        //复制整个链表        while(p!=NULL){            RandomListNode* newNode=new RandomListNode(p->label);            q->next=newNode;            q=q->next;            hash[p]=index;            copyHash[index]=q;            ++index;            p=p->next;        }        //最后的NULL节点也要加进去        hash[NULL]=index;        copyHash[index]=NULL;                //复制random指针        int i=0;        RandomListNode* r=head;        while (i
       
        random=copyHash[hash[r->random]];            ++i;            r=r->next;        }        return copyHead;    }};