[LC 138] Copy list with random pointer

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s