138. Copy List with Random Pointer
You are given head, the first node of a linked list with a twist: besides the usual val and next, every node carries a random pointer that may aim at any node in the list — or at nothing (null).
Build a deep copy: a list of brand-new nodes holding the same values, whose next and random pointers reproduce the original's wiring exactly, without ever referencing an original node. Return the head of the copy (or null for an empty list).
The judge rebuilds your returned list and checks that it shares no node with the input — handing back original nodes is rejected as not a deep copy.
Example 1:
Input: list = [3, 8, 15, 6, 2], random = [2, -1, 3, 0, 1]
Output: [3, 8, 15, 6, 2], random = [2, -1, 3, 0, 1]
Explanation: The copy must echo the original's shape: node 0's random points at node 2, node 1's random is null, node 2's at node 3, node 3's at node 0, node 4's at node 1 — but every node in the answer is newly created.
Example 2:
Input: list = [5], random = [0]
Output: [5], random = [0]
Explanation: A single node whose random pointer loops back to itself; the copy's random must loop back to the copy, not to the original.
Constraints:
- 0 ≤ n ≤ 1000
- -10⁴ ≤ Node.val ≤ 10⁴
- Each random pointer is null or targets a node within the list.
- Values may repeat — do not assume they identify a node.
Hints:
Two passes with a hash map: first create a fresh node for every original and record original → copy; second pass, wire each copy's next and random by looking up the originals in the map. Map by node identity, not by value — values can repeat.
For O(1) extra space, interleave: splice each copy right after its original (A → A' → B → B' → …). Then original.random.next is exactly the copy's random target. Unzip the two lists at the end, restoring the original.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: list = [3, 8, 15, 6, 2], random = [2, -1, 3, 0, 1]
Expected output: [3, 8, 15, 6, 2], random = [2, -1, 3, 0, 1]