题目描述

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

/*
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)
    {
        
    }
}

 

思路：

 

实现：

/*
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;
        //0 定义当前结点，为后面判断做准备
        RandomListNode currentNode = pHead;
        
        //1 先复制每个结点，复制的结点放在 被复制结点 的后面；
        while (currentNode != null){
            //1.1 创建一个新结点，新结点和旧链表的当前结点值一样；
            RandomListNode cloneNode = new RandomListNode(currentNode.label);
            //1.2获取旧链表当前结点的下一个结点
            RandomListNode nextNode = currentNode.next;
            //1.3 旧链表的当前结点 指向 新结点
            currentNode.next = cloneNode;
            //1.4 新结点 指向 旧链表的当前结点的下一个结点
            cloneNode.next = nextNode;
            //1.5 插入新结点完成后，旧链表的当前结点向后移动一个；
            currentNode = nextNode;
        }
        
        
        //2  再遍历一次链表，将旧结点的随机指针复制给新结点；遍历前先将当前结点重置头结点；
        //2.1 重置当前结点为 头结点
        currentNode = pHead;
        while (currentNode != null){
            //2.1 当前结点的下一结点的随机指针，等于当前结点的随机指针所指向结点的下一个结点
            currentNode.next.random = currentNode.random == null ? null : currentNode.random.next;
            //2.2 当前结点跳到下一个旧结点；
            currentNode = currentNode.next.next;
        }
        
        //3 将原链表和复制链表拆分开来
        //3.1 重置当前结点为 头结点
         currentNode = pHead;
        //3.2 创建一个新的复杂链表的 头结点 指向第一个 复制结点；
        RandomListNode clonePHead = pHead.next;
        while (currentNode != null){
            RandomListNode cloneNode = currentNode.next;
            currentNode.next = cloneNode.next;
            cloneNode.next = cloneNode.next == null ? null : cloneNode.next.next;
            currentNode = currentNode.next;
        }
        return clonePHead;
    }
}