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: Use a HashMap.

public RandomListNode copyRandomList(RandomListNode head) {
    if(head == null) {
        return head;
    }
    HashMap<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
    RandomListNode p = head;
    RandomListNode newhead = new RandomListNode(head.label);
    RandomListNode pn = newhead;
    map.put(p, newhead);
    p = p.next;
    while(p != null) {
        RandomListNode node = new RandomListNode(p.label);
        pn.next = node;
        map.put(p, node);
        p = p.next;
        pn = pn.next;
    } 
    p = head;
    pn = newhead;
    while(p != null) {
        pn.random = map.get(p.random);
        p = p.next;
        pn = pn.next;
    }
    return newhead;
}