Copy List with Random Pointer

 1 /**
 2  * Definition for singly-linked list with a random pointer.
 3  * struct RandomListNode {
 4  *     int label;
 5  *     RandomListNode *next, *random;
 6  *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     RandomListNode *copyRandomList(RandomListNode *head) {
12         if (!head) return NULL;
13         unordered_map<RandomListNode *, RandomListNode *> map;
14         RandomListNode dummy(0), *curNew = &dummy, *cur = head;
15         while (cur) 
16         {
17             if (map.find(cur) == map.end())
18                 map[cur] = new RandomListNode(cur->label);
19             if (cur->random && map.find(cur->random) == map.end())
20                 map[cur->random] = new RandomListNode(cur->random->label);
21             curNew->next = map[cur];
22             curNew = curNew->next;
23             curNew->random = map[cur->random];
24             cur = cur->next;
25         }
26         return dummy.next;
27     }
28 };