Well, since we need to make a deep copy of the list and nodes in the list have a random pointer that may point to any node in the list (or NULL), we need to maintain a mapping from each node in the origianl list to the node in the copy list. If the copy of a node already exists, just use that copy without copying it again; otherwise, create a new copy and add it to the mapping.

The following code is pretty straight-forward.

1 class Solution { 2 public: 3     RandomListNode *copyRandomList(RandomListNode *head) { 4         if (!head) return NULL; 5         mp[head] = new RandomListNode(head -> label); 6         RandomListNode* run = head; 7         RandomListNode* temp = mp[head]; 8         while (run) { 9             /* Process the next pointer */10             if (run -> next) {11                 if (mp.find(run -> next) == mp.end())12                     mp[run -> next] = new RandomListNode(run -> next -> label);13                 temp -> next = mp[run -> next];14             }15             /* Process the random pointer */16             if (run -> random) {17                 if (mp.find(run -> random) == mp.end())18                     mp[run -> random] =  new RandomListNode(run -> random -> label);19                 temp -> random = mp[run -> random];20             }21             run = run -> next;22             temp = temp -> next;23         }24         return mp[head];25     }26 private:27     unordered_map
     
       mp;28 };
     

This code also has a very concise and easy-to-understand recursive solution as follows.

1 class Solution { 2 public: 3     RandomListNode *copyRandomList(RandomListNode *head) { 4         if (!head) return NULL; 5         if (mp.find(head) != mp.end()) 6             return mp[head]; 7         RandomListNode* node = new RandomListNode(head -> label); 8         mp[head] = node; 9         node -> next = copyRandomList(head -> next);10         node -> random = copyRandomList(head -> random);11         return mp[head];12     }13 private:14     unordered_map
     
       mp;15 };
     

has a clever solution using O(1) extra space, which is rewritten below in C++.

1 class Solution { 2 public: 3     RandomListNode *copyRandomList(RandomListNode *head) { 4         if (!head) return NULL; 5         RandomListNode* run = head; 6         /* Insert the copy of each node after it. */ 7         while (run) { 8             RandomListNode* copy = new RandomListNode(run -> label); 9             copy -> next = run -> next;10             run -> next = copy;11             run = run -> next -> next;12         }13         /* Set the random pointer for each copy. */14         run = head;15         while (run) {16             if (run -> random)17                 run -> next -> random = run -> random -> next;18             run = run -> next -> next;19         }20         /* Extract the copy list. */21         RandomListNode* new_head = new RandomListNode(0);22         RandomListNode* new_run;23         run = head;24         new_head -> next = head -> next;25         while (run) {26             new_run = run -> next;27             run -> next = new_run -> next;28             if (run -> next)29                 new_run -> next = new_run -> next -> next;30             run = run -> next;31         }32         return new_head -> next;33     }34 };