A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. Return a deep copy of the list.

The following solution uses a HashMap to keep track of the nodes that has been visitied. The algorithm has 2 lists: list A is the original list to be copied, and List B is the new copy. The algorithm visits List A one node at a time.