Java复杂链表的复制详解

class Solution {
    public node copyRandomList(Node head) {
        if(head == null) {
            return null;
        }        
        //1.复制各个链表，并连接
        Node cur = head;
        while (cur != null) {
            //复制
            Node prev = new Node(cur.val);
            prev.next = cur.next;
            //连接
            cur.next = prev;
            //往后走
            cur = prev.next;
        }
        //2.构建各新节点的random 指向
        cur = head;
        while (cur != null) {
            if (cur.random != null) {
                cur.next.random = cur.random.next;
            }
            cur = cur.next.next;
        }
        //3.拆分复制的链表
        cur = head.next;
        Node node = head;
        Node nodeNext = head.next;
        while (cur.next != null) {
            node.next = node.next.next;
            cur.next = cur.next.next;
            node = node.next;
            cur = cur.next;
        }
        node.next = null;//尾节点
        return nodeNext;//返回新链表的头结点
    }
}