Copy List With Random Pointer

Given a linked list where every node carries val, a next pointer, and a random pointer to an arbitrary node (or null), construct a deep copy — new nodes, identical structure. The machine cannot share nodes with the original, and random may point anywhere, even forward.

The key insight: a hash map of original→clone works, but there is an O(1)-space variant — interleave each clone directly after its original. Then every original's random target is immediately followed by its clone, so wiring the clone's random is a single pointer hop: clone.random = original.random.next.

Approach:

1. Pass one: for each original node, insert a clone between it and its successor.
2. Pass two: wire each clone's random via the interleaving trick.
3. Pass three: unweave the list — restore original next links, extract clones.

def copy_random_list(head):
    node = head
    while node:
        clone = Node(node.val, node.next)
        node.next = clone
        node = clone.next
    node = head
    while node:
        if node.random:
            node.next.random = node.random.next
        node = node.next.next
    dummy = tail = Node(0)
    node = head
    while node:
        tail.next = node.next
        tail = tail.next
        node.next = tail.next
        node = node.next
    return dummy.next

Time: O(n), three passes. Space: O(n) for clones, O(1) auxiliary.

Trickiest edge case: random pointing to null — the wiring pass must guard with if node.random before dereferencing .next.