Copy List with Random Pointer

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.

Solution:
What is deep copy? It occurs when an object is copied along with the objects to which it refers.
Use a hash map to avoid infinite loops.

public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        // map from old list to new list, to ganrantee visit each node only once
        HashMap map = new HashMap();
        return helper(head, map);
    }
    public RandomListNode helper(RandomListNode head, HashMap map){
        if(head == null)
            return head;
        if(map.containsKey(head))
            return map.get(head);
            
        RandomListNode node = new RandomListNode(head.label);
        map.put(head, node);
        node.next = helper(head.next, map);
        node.random = helper(head.random, map);
        
        return node;
    }
}