用O(1)空间复杂度实现复制（深拷贝）有随机指针的链表

如题目所述要求空间复杂度为O(1)，所以此处就不讨论使用其它数据结构辅助解题的方法了。

最初看到题时，钻了牛角尖想着拷贝后俩链表就是分开的。虽然知道困难是在于确定新节点随机指针，但总是没思路。下午去海边溜达时，突然想到它们最初也是可以是不分开啊！如果生成的新节点先放在老节点与老节点下个节点的中间，然后再次遍历的时候就能确定新节点随机指针的指向了。

过程示意图

示例代码

public ListRandomNode copy(ListRandomNode head) {
        if (head == null) return null;
        // 1. 将生成的新节点插入原来链表中
        ListRandomNode curr = head;
        while (curr != null) {
            ListRandomNode temp = new ListRandomNode(curr.value, curr.next);
            curr.next = temp;
            curr = temp.next;
        }
        // 2. 遍历链表，定位新节点的随机指针指向
        curr = head;
        while (curr != null) {
            if (curr.random != null) {
                curr.next.random = curr.random.next;
            }
            curr = curr.next.next;
        }
        // 3. 拆分新老链表的节点
        ListRandomNode newNode;
        ListRandomNode newHead = head.next;
        curr = head;
        while (curr != null) {
            // 连接老链表
            newNode = curr.next;
            curr.next = newNode.next;
            // 连接新链表
            if (curr.next != null) {
                newNode.next = curr.next.next;
            } else {
                newNode.next = null;
            }
            curr = curr.next;
        }
        return newHead;
    }

    class ListRandomNode {

        private int value;

        ListRandomNode next;

        ListRandomNode random;

        public ListRandomNode(int value, ListRandomNode next) {
            this.value = value;
            this.next = next;
        }
    }