public static RandomListNode copyRandomList(RandomListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        HashMap<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
        
        /* shallow copy the list */
        RandomListNode dummy = new RandomListNode(0);
        RandomListNode tail = dummy;
        RandomListNode p = head;
        while (p!= null) {
            RandomListNode newNode = new RandomListNode(p.label);
            newNode.next = newNode.random = null;
            tail.next = newNode;
            map.put(p, newNode);
            p = p.next;
        }
        
        /* copy random pointer */
        RandomListNode it = head;
        while (it != null) {
            RandomListNode newNode = map.get(it);
            RandomListNode newrandom = map.get(it.random);
            newNode.random = newrandom;
            it = it.next;
        }
        return dummy.next;
    }