Why it works
- A random link may point forward, to a node whose copy does not exist yet. So the first pass only makes the copies, and the second pass links them, when every copy is there.
- The map from an old node to its copy is what makes each link one lookup: the copy of node.random is copy[node.random], with no search through the list.
- Every link of a copy is taken from the map, and the map holds only new nodes, so nothing in the copy can lead back into the old list.
Complexity
Time O(n): two passes over the list, each lookup in the map is O(1). Memory O(n): the map holds one entry per node, besides the copy itself.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗