138. Copy List with Random Pointer

    /*
     * 138. Copy List with Random Pointer 
     * 2016-5-22 by Mingyang
     * 要遍历两次，第一次用来找到所有的next节点，并且把新旧节点全部存在hashmap里面，第二次遍历就是找出所有的random节点
     * 刚开始的时候自己做的以为跟clone graph一样的原理，需要建一个queue，后面发现这里的next自带queue功能
     * 不过这里奇特的地方就在于需要遍历两次，因为这里的random是指向另外的一个节点！！！所以需要依次找到那个节点！！！
     */
    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null)
            return null;
        HashMap<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
        RandomListNode p = head;
        while (p != null) {
            map.put(p, new RandomListNode(p.label));
            p = p.next;
        }
        p = head;
        while (p != null) {
            map.get(p).random = map.get(p.random);
            map.get(p).next = map.get(p.next);
            p = p.next;
        }
        return map.get(head);
    }