Medium Hash Clone Linked Lists
In plain English: Clone a linked list where each node also has a random pointer to any other node in the list.
First pass: create a clone of each node and store the mapping old->new in a hash map. Second pass: wire up next and random pointers using the map. The map is the key to handling random pointers.
Prompt
A linked list has nodes with a next pointer and a random pointer (which can point to any node or null). Return a deep copy of the list.
Try to write it from scratch before scrolling down.
Solution
class Node:
def __init__(self, val=0, next=None, random=None):
self.val = val
self.next = next
self.random = random
def copy_random_list(head):
if not head:
return None
old_to_new = {}
# Pass 1: create cloned nodes
cur = head
while cur:
old_to_new[cur] = Node(cur.val)
cur = cur.next
# Pass 2: set next and random pointers
cur = head
while cur:
clone = old_to_new[cur]
clone.next = old_to_new.get(cur.next)
clone.random = old_to_new.get(cur.random)
cur = cur.next
return old_to_new[head]
# Test: list 7->13->11, 13.random=7, 11.random=13
# deep copy preserves structure with new node objects