Intuitive solution:
Two rounds: first round, copy all nodes and link them as a list (copy the “next” pointer of each node), store all nodes in a map (key: node label, value the pointer to this node); second round, copy the “random” pointer of each node.
Solution with less space:
Remove the map, link each copied node with its original node. Three rounds: first round, copy all nodes and link the copy with the original node; second round, copy the random pointer from the original nodes to the copied nodes; third round, extract the copied link list and restore the original link list.
The second solution requires less space, and rans faster. Less space does not always mean more running time.
Advertisements
