题目描述

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

题解

  • 在原链表上对每个节点进行复制。
    image.png
  • 对复制的节点的random指针进行复制
    image.png
  • 从链表中拆分出新链表
    image.png
/*
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;
    }
}