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<RandomListNode*, RandomListNode*> 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<RandomListNode*, RandomListNode*> mp; 15 };
This link 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 };
