Copy List with Random Pointer

题目：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.

思路：

思路还真的不容易想出来，先是把所有节点存到hash表，就是为了方便之后某一个节点的 random 节点能够很快找到。

接下来就是复制原始链表，不复制next 那一部分。

最后就是从头开始，找  random ，这个时候，如果 random 存在，放大hash函数里面，通过 vector 数组能够很快知道是哪个节点，直接链接过去即可。

代码：

/**
 * Definition for singly-linked list with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        RandomListNode *p=NULL,*t=NULL,*h=NULL;
        
        unordered_map<RandomListNode *,int>m;
        int pos=0;
        for(p=head;p!=NULL;p=p->next,pos++){
            m[p]=pos;
        }
        
        //开始克隆，不进行任何的random变换
        vector<RandomListNode *>v;
        for(p=head;p!=NULL;p=p->next){
            RandomListNode *node=new RandomListNode(p->label);
            v.push_back(node);
            if(h==NULL){
                h=t=node;
            }else{
                t->next=node;
                t=t->next;
            }
        }
        
        //开始操作那些random链表
        t=h;
        for(p=head;p!=NULL&&t!=NULL;p=p->next,t=t->next){
            if(p->random!=NULL){
                t->random=v[m[p->random]];
            }
        }
        
        return h;
    }
};