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

遍历原有的链表的每个节点的同时，复制节点的random和next。不需要用到其它的什么容器来存储，因此时间复杂度较低，超过百分之九十。

public class SolutionJZ25 {
    public RandomListNode Clone(RandomListNode pHead) {
        //为空就返回
        if(pHead==null) return null;
        //下面10行为复制第一个节点。并且用一个res来指向第一个节点，用来作为返回的头结点
        RandomListNode newNode = new RandomListNode(pHead.label);
        if (pHead.random != null) {
            newNode.random = new RandomListNode(pHead.random.label);
        }
        if (pHead.next != null) {
            newNode.next=new RandomListNode(pHead.next.label);
        }
        RandomListNode res=newNode;
        newNode=newNode.next;
        pHead = pHead.next;

        //下面的循环为：如果pHead节点不为空，就复制它的random和next。然后pHead指针和newNode指针下移到各自的next。直到走到链表的结尾
        while (pHead != null) {
            if (pHead.random != null) {
                newNode.random = new RandomListNode(pHead.random.label);
            }
            if (pHead.next != null) {
                newNode.next=new RandomListNode(pHead.next.label);
            }
            newNode=newNode.next;
            pHead = pHead.next;
        }
        return res;
    }
}