【面试题25-复杂链表的复制】

剑指offer第二十五题。

题目描述

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

解题思路

图4.8 是一个含有5 个结点的复杂链表。图中实线箭头表示next 指针，虚线箭头表示随机 引用。为简单起见，指向null 的指针没有画出。

理解了上面，下面我们就根据这个过程来实现一下。

我的答案

/*
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)
    {
        //0.判断空的情况
        if(pHead == null){
            return null;
        }
        
        //1.复制结点
        RandomListNode node = pHead;
        while(node != null){
            //保存下一个结点next-->新建一个克隆结点-->指定node.next到克隆结点
            //-->克隆结点的next指向next结点-->更新node为next结点
            RandomListNode next = node.next;
            RandomListNode cloneNode = new RandomListNode(node.label);
            node.next = cloneNode;
            cloneNode.next = next;
            node = next;
        }
        
        //2.复制随机引用
        node = pHead;
        while(node != null){
            if(node.random != null){
                node.next.random = node.random.next;
            }
            node = node.next.next;
        }
        
        //3.分离两个链表
        node = pHead;
        //记录复制的链表的头结点
        RandomListNode newHead = pHead.next;
        while(node != null){
            RandomListNode currNode = node.next;
            //更新原结点的next
            node.next = currNode.next;
            //更新克隆结点的next
            if(currNode.next != null){
                currNode.next = currNode.next.next;
            }
            //更新原结点指针
            node = node.next;
        }
        
        return newHead;
    }
}