[Leetcode] Copy List with Random Pointer

Problem 

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.

Algorithm 

This problem is similar to the graph clone problem. First, we traverse the linked list moving along next pointer. Whenever we discover a new node, we create a copy of it. A hash map is used to map the original node to the copied node, for a later reference. Then we iterate the original list and the copied list simultaneously. For pair of nodes u and u's mirror, we can find u.random. Using the built hash map we can find the mirror of u.random, then point u's mirror to the mirror of u.random.
                                           ____
                                           |       |
Original List               A - > B -> C
HashMap                     |        |       |
Copied List                A' -> B' -> C'
                                           |____|

A hash map can map from one object to another, which can be used when we need fast reference. 

Code