1031. Copy the Referral Chain
A referral program lists its members in sign-up order, linked by next. Every member also has a random link to one other member (possibly themselves) who influenced them most, or null if nobody did. Given head, the first member, build a deep copy of the whole chain: brand new nodes with the same values, where each new node's next and random point to the new nodes in the same positions as in the original.
The original chain must stay unchanged and the copy must not share any node with it. Return the head of the copy, or null for an empty chain. Aim for O(n) time; O(n) extra space is fine.
Example 1
- Input:
- head = [[4,2],[7,0],[1,null]]
- Output:
- [[4,2],[7,0],[1,null]]
- Explanation:
The copy has values 4, 7, 1; the first node's random points to the third node, the second node's random to the first, and the last has none, all within the copy.
Example 2
- Input:
- head = [[9,1],[6,1],[3,0],[2,null]]
- Output:
- [[9,1],[6,1],[3,0],[2,null]]
- Explanation:
Two nodes share the same random target (the second node); the copy keeps that sharing among its own nodes.
Constraints
0 ≤ chain length n ≤ 105
-104 ≤ node value ≤ 104
random is null or points to any node of the chain.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n)
- Space
- O(n)