Copy List with Random Pointer

Use a two-pass map solution unless the interviewer specifically asks to optimize extra space. In pass one, allocate a clone for every original node and store original-to-clone mappings. In pass two, set each clone's next and random by looking up the original targets, preserving nulls. This guarantees that every pointer in the copy targets a copy, not an original. The solution is O(n) time and O(n) extra space. For O(1) extra space, weave clone nodes after originals, set clone.random using original.random.next, then unweave the two lists while restoring original next links. Explain the invariant before manipulating pointers and test self-random, backward-random, and null-random cases. A shallow copy that reuses random targets is incorrect.