The clever space approach interleaves copies with originals:
Insert copy of each node right after the original:
Set random pointers: copy.random = original.random.next
Separate the lists
# Step 1: Interleave
current = head
while current:
copy = new Node(current.val)
copy.next = current.next
current.next = copy
current = copy.next
# Step 2: Set random
current = head
while current:
if current.random:
current.next.random = current.random.next
current = current.next.next
# Step 3: Separate
dummy = new Node(0)
copyCurrent = dummy
current = head
while current:
copyCurrent.next = current.next
current.next = current.next.next
copyCurrent = copyCurrent.next
current = current.next
return dummy.next