/**

 * 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) {

        unordered_map<RandomListNode*,RandomListNode*> umap;

        RandomListNode* newHead  = NULL;

        RandomListNode* cur      = head;

        RandomListNode* node_pre = NULL;

        RandomListNode* node     = NULL;

        while(cur){

            node      = new RandomListNode(cur->label);

            umap[cur] = node;

            cur == head ? newHead = node :node_pre->next = node;

            node_pre  = node;

            cur       = cur->next;

        }

        cur = head;

        while(cur){

            umap[cur]->random = cur->random ? umap[cur->random] : NULL;

            cur               = cur->next;

        }

        return newHead;

    }

};