[Leetcode] 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.

一道相对比较复杂的链表题。第一种思路是使用HashMap来存储原来的节点和新生成的节点之间的对应关系，通过这个对应关系来恢复新生成的节点的random所指向的节点。这种方法的空间复杂度为O(n)。

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

另一种方法比较巧妙，通过改变原来的链表，即将新生产的节点插入在原来的节点后面，然后第二遍扫描的时候来恢复random的值，然后第三遍扫描将原来的节点和新生产的节点分离，从而得到一个deep copy原来的链表。

public RandomListNode copyRandomList(RandomListNode head) {
        if(head == null) return head;
        RandomListNode temp = head;
        
        while(temp != null) {
            RandomListNode node = new RandomListNode(temp.label);
            node.next = temp.next;
            temp.next = node;
            temp = node.next;
        }
        temp = head;
        while(temp != null) {
            if(temp.random != null) {
                temp.next.random = temp.random.next;
            }
            temp = temp.next.next;
        }
        RandomListNode nhead = head.next, ntemp = head.next;
        temp = head;
        while(head != null) {
            temp.next = ntemp.next;
            temp = temp.next;
            if(temp == null) break;
            ntemp.next = temp.next;
            ntemp = ntemp.next;
        }
        
        return nhead;
    }