复杂链表的复制（Java）

原题链接
1新建链表（时间O（N^2） 空间O（1））
思路来源：只有构建了完整的新链表后，才能确定每个结点的地址，才能确定next域。
源码：

class Solution {
    public Node copyRandomList(Node head) {
 //1计算链表的长度
 //2先建立一个与其长度相同的ramdom域的链表
 //3建立两个指针确认每个结点的random域指向的结点 并把相应的信息同步到新链表中
        Node cur = head;//遍历原链表的指针
        int len = 0;
        while (cur != null) {
            cur = cur.next;
            len++;
        }
        Node newHead = new Node(-1);//新节点的头
        Node newTail = newHead;//新节点的尾
        cur = head;
        while (cur != null) {
            newTail.next = new Node(cur.val);
            newTail = newTail.next;
            cur = cur.next;
        }
        cur = head;
        Node curSearch = head;//用于定位旧链表的每个结点的指向的random
        Node newSearch = newHead.next;//用于定位新链表的每个结点的指向的random
        Node curNew = newHead.next;//遍历新链表的指针
        while (cur != null) {
            //search初始化
            curSearch = head;
            newSearch = newHead.next;
            while (curSearch != cur.random) {
                curSearch = curSearch.next;
                newSearch = newSearch.next;
            }
            curNew.random = newSearch;
            cur = cur.next;
            curNew = curNew.next;
        }
        return newHead.next;
    }
}

2复制并分割链表（时间O（n）空间O（N）目前的理想解法）
思路来源：同样是创建了新链表的每个结点后才为random域赋值 不过使用了插入和分割链表的算法，让寻找random变得容易

class Solution {
    public Node copyRandomList(Node head) {
//1为每个结点后都插入一个新节点 且每个新节点都是原结点的值 例 1 -> 2 -> 3    1 -> 1 -> 2 -> 2 -> 3 -> 3
 //这样的好处是可以一步就定位到新链表的random域
 //2利用cur.random.next = cur.next.random遍历每个结点
//3将链表一份为二
        if (head == null) return null;
        Node cur = head;
        for (cur = head; cur != null; cur = cur.next.next) {
            Node newNode = new Node(cur.val);
            newNode.next = cur.next;
            cur.next = newNode;
        }
        for (cur = head; cur != null; cur = cur.next.next) {
            if (cur.random != null) {
                cur.next.random = cur.random.next;
            } else {
                cur.next.random = null;
            }
            
        }
        Node newHead = head.next;
        for (cur = head; cur != null && cur.next != null; cur = cur.next) {
            Node newCur = cur.next;
            cur.next = cur.next.next;
            if (newCur.next != null) {
                newCur.next = newCur.next.next;
            }
        }
        return newHead;
    }
}