Interleaving Approach

The clever $O(1)$ space approach interleaves copies with originals:

$1.$ Insert copy of each node right after the original: $A \to A' \to B \to B' \to C \to C'$

$2.$ Set random pointers: copy.random = original.random.next

$3.$ 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