Deep copy a linked list with random pointer

Question:Given a linked list which has a next pointer pointing to the next element in the list and a random pointer pointing to the random element in the list. Implement a method to deep copy this linked list such that the random pointer still copies to the same node in the new list.
1. Create a copy of each node and insert the element next to the original node, iterate through the list.
2. Now the new list has 2N elements (assuming original one has N elements). Then assign the random pointer’s next node to the copied node’s random pointer. Iterate through the list.
3. Now break the list in two lists, original and new.

This logic is implemented in the method DeepCopy in the page.

Leave a Reply