Given a linked list which has random pointer along with next pointer. The random pointer can point to any node in the list. So, how do we create a deep copy of this linked list? and write corresponding code.
The basic approach is to create copy of the list, and maintain a map of original node and its corresponding copy node (hash table) in first iteration. And in the second iteration update the random pointers of the new list using hash table. The approach takes O(n) time complexity with O(N) additional memory along with copy of linked list.
Below is approach 2, with O(1) memory, and by using memory only for creating the copy of linked list. Below is the gist of the basic solution:
1. In the first iteration create copy of the linked list, along with that make sure original list nodes points to their corresponding new copy node.
2. In the second iteration, update the random pointer of copied list
3. detach the lists
Below is the corresponding code in C# which illustrates the above idea: