题解 | #复杂链表的复制#

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

    RandomListNode(int label) {
        this.label = label;
    }
}
*/
import java.util.* ;
public class Solution {
    public RandomListNode Clone(RandomListNode pHead) {
        if(pHead == null) {
            return null ;
        }
        RandomListNode p = pHead ;
        while(p != null) {//在原链表总插入新连表（只管next）
            RandomListNode newNode = new RandomListNode(p.label) ;
            newNode.next = p.next ;
            p.next = newNode ;
            p = newNode.next ;
        }
        p = pHead ;
        while(p != null) {//根据原链表的random去设置新链表的random
            RandomListNode ran = p.random ;
            if(ran != null) {//不是每个结点都一定有random
                p.next.random = ran.next ;
            }
            p = p.next.next ;
        }
        RandomListNode res = pHead.next ;
        pHead.next = null ;//与原链表断开一定要彻底，不然会报错
        RandomListNode t = res ;
        while(t.next != null) {//将原链表与新链表断开
            t.next = t.next.next ;
            t = t.next ;
        }
        return res ;
    }
}