138.复制带随机指针的链表

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。且不能修改原链表。

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

1. 先用O(n)时间构造新链表的value值和next指针。之后再用O($n^2$)时间连接新链表的random指针。方法是旧链表指针和新链表指针同步走，旧链表指针到达旧链表中指向的random节点时，新链表此时指向的即为对应random节点。

2. 开辟一个O(n)大小的队列来保存旧链表的next指针，第一次构建新链表时，令新链表的random指针指向旧链表的random指针，旧链表的next指针指向新链表中对应的节点。第二次遍历新链表令p.random=p.random.next;即可让新链表中的random指向对应的节点。之后再通过队列还原旧链表的next指针。时间复杂度为O(n)。

3. 方法2的问题在于恢复next指针时，一个链表恢复后另一个链表就恢复不了只能开辟空间保存。如果是同时恢复链表next指针的话就不需要另外开辟空间，方法是构建新链表时新节点插入旧链表中(插空)，形成旧链表节点->新链表节点->旧链表节点的一个交错链表，新链表random指针指向旧链表对应位置节点的random指针。这样可以根据旧链表节点的next指针找到新链表中对应位置的节点。最后再遍历一次整个大链表把新旧链表分开。

public Node copyRandomList(Node head) {
    if(head==null) return null;
    Node p=head,pne=p.next,copyhead=null; //copyhead新链表头
    while(pne!=null) //p旧链表节点。插入新节点
    {
        Node node=new Node(p.val);
        if(p==head) copyhead=node;
        p.next=node;
        node.next=pne;
        node.random=p.random;
        p=pne;
        pne=pne.next;
    }
    Node node=new Node(p.val);//插入最后一个
    node.random=p.random;
    node.next=null;
    p.next=node;
    p=copyhead=head.next; //防止原链表只有一个节点，copyhead为空情况
    while(p!=null) //找到新链表random节点
    {
        if(p.random!=null)
        p.random=p.random.next;
        p=p.next;
        p=p!=null?p.next:p;
    }
    p=copyhead;
    Node headnode=head;
    while(headnode!=null)  //新旧链表分开
    {
        headnode.next=p.next;
        if(p.next!=null)
        p.next=p.next.next;
        headnode=headnode.next;
        p=p.next;
    }
    return copyhead;
}