35 复杂链表的复制

牛客

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）。 下图是一个含有5个结点的复杂链表。图中实线箭头表示next指针，虚线箭头表示random指针。为简单起见，指向null的指针没有画出。

/*
public class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}
*/
public RandomListNode Clone(RandomListNode pHead) {
    if(pHead==null) return null;

    //每个节点复制一份
    RandomListNode r=pHead;
    RandomListNode t=null;
    while(r!=null){
        t=r.next;
        r.next=new RandomListNode(r.label);
        r.next.next=t;
        r=r.next.next;
    }

    //复制 random 
    r=pHead;
    while(r!=null){
        if(r.random!=null) r.next.random=r.random.next;
        r=r.next.next;
    }

    //拆分
    r=pHead;
    RandomListNode ret=r.next;
    while(r!=null){
        t=r.next;
        r.next=t.next;
        r=r.next;
        if(r!=null){
            t.next=r.next;

        }
    }

    return ret;
}