Copy List with Random Pointer

完全复制一个具有随机指针（指向任意一个节点或者为null）的链表。

实现方法很多，这里给出一个空间复杂度O(1)，时间复杂度O(n)的算法。它利用原来的链表对新建链表的随机指针进行定位。

算法如下:

/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */
public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) {
            return null;
        }
        
        RandomListNode itr = head;
        RandomListNode next;
        
        /**
         * 该循环将复制的节点连接到被复制的节点后面，形成
         * 原节点1 -> 复制节点1 -> 原节点2 -> 复制节点2的情况，
         * 保留了位置信息
         */
        while (itr != null) {
            next = itr.next;
            
            RandomListNode copy = new RandomListNode(itr.label);
            itr.next = copy;
            copy.next = next;
            
            itr = next;
        }
        
        //此处循环根据原节点可以很方便的把复制节点的random指针找到
        itr = head;
        while (itr != null) {
            if (itr.random != null) {
                itr.next.random = itr.random.next;
            } else {
                itr.next.random = null;
            }
            
            itr = itr.next.next;
        }
        
        //将原链表还原，新链表重新连接
        RandomListNode copyHead = new RandomListNode(0);
        RandomListNode itrCopy = copyHead;
        itr = head;
        while (itr != null) {
            itrCopy.next = itr.next;
            itrCopy = itrCopy.next;
            itr.next = itrCopy.next;
            itr = itr.next;
        }
        
        return copyHead.next;
    }
}