A linked list has nodes with an additional random pointer that can point to any node in the list or null. Create a deep copy of this list.
Example: Node 1's random points to node 3, node 2's random points to node 1. Your copy must have the same structure with new nodes.
The challenge: when copying node , you might need to set its random pointer to node , but might not be copied yet.
Two approaches: space with a hash map, or space with interleaving. Constraints: up to nodes, values from to .