复杂链表的复制

题目描述

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

题解

• 在原链表上对每个节点进行复制。
  
• 对复制的节点的random指针进行复制
  
• 从链表中拆分出新链表
  

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

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

        RandomListNode tempHead=pHead;

        // 在原链表上复制next
        while(tempHead!=null){
            RandomListNode temp=new RandomListNode(tempHead.label);
            temp.next=tempHead.next;
            tempHead.next=temp;
            tempHead=tempHead.next.next;
        }

        // 复制random指针
        RandomListNode originHead=pHead;
        while(originHead!=null){
            originHead.next.random=originHead.random==null?null:originHead.random.next;
            originHead=originHead.next.next;
        }

        // 从原链表拆分出新链表
        originHead=pHead;
        RandomListNode res=pHead.next;
        while(originHead!=null){
            RandomListNode newHead=originHead.next;
            originHead.next=originHead.next.next;
            newHead.next=newHead.next==null?null:newHead.next.next;
            originHead=originHead.next;
        }
        return res;
    }
}