题目描述

请实现一个函数可以复制一个复杂链表。

在复杂链表中，每个结点除了有一个指针指向下一个结点外，还有一个额外的指针指向链表中的任意结点或者null。

注意：

函数结束后原链表要与输入时保持一致。

复制节点 法

public ListNode copyRandomList(ListNode head) {
        if(head == null) return null;
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        while (head != null) {
            ListNode next = head.next;
            ListNode newHead = new ListNode(head.val);
            head.next = newHead;
            newHead.next = next;

            head = head.next.next;
        }

        head = dummy.next;
        while (head != null) {
            if(head.random == null) head.next.random = null;
            else{
                head.next.random = head.random.next;
            }
            head = head.next.next;
        }

        head = dummy.next;
        ListNode newHead = head.next;
        ListNode res = newHead;
        while(head != null) {
            ListNode next = head.next.next;
            head.next = next;
            head = head.next;
            if(head!=null){
                newHead.next = next.next;
                newHead = newHead.next;
            }
        }
        head = dummy.next;
        dummy.next = null;
        return res;
    }