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.

和graph copy一样的，先用一个hash table存一下，先copy 边，再copy线。。。不二法门。。。

/**
 * 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:
    /**
     * @param head: The head of linked list with a random pointer.
     * @return: A new head of a deep copy of the list.
     */
    RandomListNode *copyRandomList(RandomListNode *head) {
        // write your code here
        if (!head)
            return 0;
        unordered_map<RandomListNode*, RandomListNode*> map;
        RandomListNode* root=head;
        while(head){
            map[head]=new RandomListNode(head->label);
            head=head->next;
        }
        head=root;
        while(head){
            if (head->next)
                map[head]->next=map[head->next];
            if (head->random)
                map[head]->random= map[head->random];
            head=head->next;
        }
        return map[root];
    }
};