Medium: Clone a linked list with random pointers

Two valid approaches

The simplest solution maps every original node to its clone in a first pass, then uses the map to assign both next and random in a second pass. That is O(n) time and O(n) space. If constant auxiliary space is required, interleave: insert each clone immediately after its original, set clone.random = original.random?.next, then detach alternating nodes to restore the original list and produce the clone list.

Why interleaving works

After insertion, the clone of any original u is always u.next; therefore the clone of u.random is u.random.next when it exists. This gives direct access without a map. Be meticulous during detachment so both original and copied next chains are repaired. Test null heads, one node, self-random links, and random links backward or forward. Do not allocate a clone per pointer edge: cloning is per node, and shared random targets must remain shared.