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.

思路一(hashtable)

1. hashtable 存每个listnode作为key, 对应的copy作为value
2. 遍历旧节点, 建立新节点间的关系
3. 时间复杂度 O(n)
4. 空间复杂度 O(n)

    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) return null;
        // 1. hashmap stores old and new
        Map<RandomListNode, RandomListNode> map = new HashMap<>();
        RandomListNode curt = head;
        while (curt != null) {
            RandomListNode newNode = new RandomListNode(curt.label);
            map.put(curt, newNode);
            curt = curt.next;
        }
        // 2. build relation
        curt = head;
        while (curt != null) {
            map.get(curt).next = map.get(curt.next);
            map.get(curt).random = map.get(curt.random);
            curt = curt.next;
        }

        return map.get(head);
    }

思路二(two pointers)

1. 建立所有next的点
2. 关键: 如何解决不知道random在哪里
   1. 1 -> 1' -> 2 -> 2'
   2. 这样就知道了
3. 时间复杂度 O(n)
4. 空间复杂度 O(1)

    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) return null;

        // 1. build all next nodes and their relation
        RandomListNode curt = head;

        while (curt != null) {
            RandomListNode next = curt.next;
            curt.next = new RandomListNode(curt.label);
            curt.next.next = next;
            curt = curt.next.next;
        }

        // 2. build all random nodes' relation
        curt = head;
        while (curt != null) {
            if (curt.random != null)
                curt.next.random = curt.random.next;
            curt = curt.next.next;
        }



        // 3. split new and old
        RandomListNode dummy = new RandomListNode(0);
        RandomListNode node = dummy;
        curt = head;
        while (curt != null) {
            node.next = curt.next;
            node = node.next;
            curt = curt.next.next;
        }
        return dummy.next;
    }