Each node has a next pointer and a random pointer to any node or null. Make a deep copy of the whole list.
DSA Animator › DSA Revision › Linked List › Copy List with Random Pointer
Remember: put each copy right after its original. Then the copy of a node's random is just random dot next. The video solves Copy List with Random Pointer (LeetCode 138, Medium) with the Interleaving pattern from the Linked List topic, and you can replay every step in the interactive Copy List with Random Pointer animation.
Each node has a next pointer and a random pointer to any node or null. Make a deep copy of the whole list.
For nodes 7, 13, 11, 10, 1, the random pointers go to null, 7, 1, 11 and 7. The copy must have the same shape, using only new nodes.
A hash map from each old node to its copy works in two passes. But it uses O of n extra space.
First, insert each copy right after its original, so the list alternates old and new. Then each copy's random is the original's random dot next. Finally, split the list back into the original and the copy.
Weave in the copies: 7, 7 prime, 13, 13 prime, and so on. 13's random is 7, so 13 prime's random is 7's next, which is 7 prime. In the same way, 11 prime points to 1 prime, 10 prime to 11 prime, and 1 prime to 7 prime. Unweave the list, restoring the original next pointers. The copy is 7, 13, 11, 10, 1 with the same random pointers.
In code, the first loop inserts a copy after each node. The second loop sets copy dot random to node dot random dot next, if random is not null. The third loop splits the two lists, so it's O of n time and O of 1 extra space.
Remember: put each copy right after its original. Then the copy of a node's random is just random dot next.