Copy list with random pointer

Each node has val, next and random, where random points to any node in the list or is null. Return a deep copy: new nodes with the same values, whose next and random pointers lead to the corresponding new nodes. No pointer in the copy may lead to an original node.

Before you code

Copying next is easy. The problem is random: when you copy a node, the node its random points to may not have been copied yet. You need a way to get from any original node to its copy.

Hints

1. Two passes with a hash map: first create a copy of every node and store original → copy; then set each copy's next and random by looking up the originals' targets.
2. O(1)-extra-space version: insert each copy right after its original (A → A' → B → B'). Then A'.random = A.random.next. Finally separate the two lists, restoring the original.
3. Test with a random that points to the node itself and one that points backward.

Production & complexity notes

When solving Copy list with random pointer on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Insert, delete and the dummy head to reinforce the underlying pattern.

What it practices

Careful pointer bookkeeping across two lists, from Insert, delete and the dummy head.