29.复杂链表的复制

题目：把链表复制下来
难点：除了常规的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)
    {
        if(pHead==nullptr)
            return nullptr;
        map<RandomListNode *,RandomListNode *> rec;
        RandomListNode *cur=pHead;
        while(cur!=nullptr){
            RandomListNode *node=new RandomListNode(cur->label);
            rec.insert(make_pair(cur,node));
            cur=cur->next;
        } 
        cur=pHead;
        while(cur!=nullptr){
            rec[cur]->next=rec[cur->next];
            rec[cur]->random=rec[cur->random];
            cur=cur->next;
        }
        return rec[pHead];
    }
};