You are given the head of a linked list where each node has a next pointer and a random pointer that can point to any node in the list or to null. Construct a deep copy of the list: brand-new nodes whose next and random pointers mirror the original structure, sharing no node object with the original.
Return the head of the copied list.
Input encoding (2 lines): the node values, then the random targets as 0-indexed positions (-1 for null). The judge verifies your copy is disjoint from the original and reports each copied node as val,randomIndex (the index the random pointer lands on within the copy, -1 for null).
- The number of nodes is in the range [0, 1000] - -10^4 <= Node.val <= 10^4 - random points to a node in the list or is null
First pass: create a copy of every node and store original → copy in a hash map. Second pass: for each original, wire its copy's next and random by looking the originals up in the map. Clean and easy to reason about, at O(n) extra space.
O(n) time, O(n) space.
Weave each copy right after its original (A → A' → B → B' → …). Now every copy sits next to its source, so copy.random = original.random.next sets randoms without a map. Finally unzip the two chains apart, restoring the original. O(1) extra space.
O(n) time, O(1) space.
