Copy List with Random Pointer

Problem

You are given the head of a singly linked list in which every node carries two pointers: next, which links the nodes in sequence, and random, which points to any node in the list or to nothing at all. Produce a deep copy of the list: a set of brand-new nodes with the same values, whose next and random pointers reproduce the original structure but reference only new nodes. Return the head of the copy. The original list must not be damaged when you return.

• The list has between 0 and 2,000 nodes.
• Node values fit in a signed 32-bit integer.
• Each random is None or points to some node in the same list (possibly the node itself).

Examples

• Nodes A(4) -> B(9) -> C(2) -> D(6) with A.random = C, B.random = None, C.random = A, D.random = D → a new list A'(4) -> B'(9) -> C'(2) -> D'(6) with A'.random = C', B'.random = None, C'.random = A', D'.random = D'. Random pointers may go forward, backward, to self, or nowhere, and in the copy they must land on copied nodes, not the originals.
• A(8) -> B(3) with A.random = A, B.random = A → A'(8) -> B'(3) with A'.random = A', B'.random = A'.
• empty list → empty list.

Hints

1. Copying next pointers is a simple walk. What makes random hard? Its target may not have been copied yet.
2. If you could look up "the copy of node X" in O(1), a second pass could fill in all random pointers.
3. Either build a map from original to copy in one pass and wire pointers in a second, or interleave each copy right after its original so that copy = original.next serves as the map, then unweave.