Copy List With Random Pointer: Hash Map First, Interleaving for O(1) Space
Copy List with Random Pointer asks for a deep copy of a linked list where each node also has a random pointer to any node or null. The difficulty is that a random pointer may point forward to a node you have not copied yet.
Answer 1: map old to new
Make one pass creating a copy of every node and storing old -> new in a dictionary. A second pass sets next and random using the map. O(n) time and O(n) space, and easy to get right.
Answer 2: interleave the copies
Insert each copy right after its original: A, A', B, B', ... Then copy.random = original.random.next, because the copy of any node is its next neighbour. Finally, unzip the two lists.
def copy_random_list(head):
cur = head
while cur:
cur.next = Node(cur.val, cur.next)
cur = cur.next.next
cur = head
while cur:
if cur.random: cur.next.random = cur.random.next
cur = cur.next.next
dummy = tail = Node(0)
cur = head
while cur:
tail.next = cur.next
tail = tail.next
cur.next = tail.next
cur = cur.next
return dummy.next
What to emphasise
Restore the original list during the unzip; interviewers often check that you did not leave the input mutated. Start with the hash map version, then offer interleaving as the space optimisation.
I keep notes like these while building the Linkjob AI app (https://www.linkjob.ai/). Disclosure: I help build Linkjob AI.