算法-35.复杂链表的复制

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
思路：
1.将当前链表的每个节点都进行一次赋值，并且插入这个节点的后面作为直接节点
2.根据random链接，对复制节点的random进行赋值，复制节点的random是原节点的random的next
3.对链表进行拆分，即将重新将第一个节点的next指向第三个节点，第三个节点的next指向第五个节点，以此类推；将第二个节点的next指向第四个节点，将第四个节点的next指向第六个节点，以此类推；最终就会变成两个链表，一个是第一个节点开始的，一个是第二个节点开始的，而从第二个节点开始的就是复制后的新的链表

    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    /**
     * 1.在每个新节点后面插入一个新节点，是当前节点的复制节点
     * 2.对复制节点的random链接进行赋值
     * 3.将整个链表进行拆分
     * @param head
     * @return
     */
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        Node cur = head;
        while (cur != null) {
            // 复制当前节点
            Node clone = new Node(cur.val);
            // 将复制节点插入到当前节点与当前节点的next中间
            clone.next = cur.next;
            cur.next = clone;
            // 将当前节点设置为clone的next，即插入之前的cur.next
            // 也就是插入后的clone.next
            cur = clone.next;
        }
        // 建立random链接
        cur = head;
        while (cur != null) {
            Node clone = cur.next;
            // 如果当前节点的random不为null
            // 则将clone的random设置为当前节点的random.next
            // 这是因为当前节点的random也已经被复制过一次并且插入到了random的后面
            if (cur.random != null) {
                clone.random = cur.random.next;
            }
            cur = clone.next;
        }
        // 拆分
        cur = head;
        Node cloneHead = head.next;
        while (cur.next != null) {
            // 取出当前节点的next
            Node next = cur.next;
            // 当前节点的next为next.next
            // 即第一个节点的next为复制插入之后的第三个节点
            // 即第二个节点的next为复制插入之后的第四个节点
            // 第三个节点的next为复制插入之后的第五个节点
            cur.next = next.next;
            // 继续遍历，cur变成第二个，第三个。。。
            cur = next;
        }
        return cloneHead;
    }