Copy List with Random Pointer (Java)

LeetCode

Copy List with Random Pointer

Total Accepted: 4935 Total Submissions: 24214

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.

Similar problem(Clone Graph)

Solution: 

This is an interesting question. Deep copy a single linked list with only next reference is easy. 

but, the tricky point is how to connect the random reference, we can not know if the node connected by the random reference exists or not when we copy node one by one. So to solve this problem, I think hashmap should be a good solution. With hashMap,do first while loop,  we copy every node in given list and keep them as a <originalNode, copiedNode> pair. then do another while loop connect these copied nodes together.