剑指Offer算法题 27:复杂链表的复制

>>强大,10k+点赞的 SpringBoot 后台管理系统竟然出了详细教程!

题目描述

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


解题思路

方法一

先和再分。

剑指Offer算法题 27:复杂链表的复制

第一步将复制的结点先接在原结点的后面(暂时称之为影子节点),这一步只需要将next指针确定连接即可。

剑指Offer算法题 27:复杂链表的复制

第二步根据原链表的random指针确定复制的链表的random指针。

剑指Offer算法题 27:复杂链表的复制

第三步将得到的一个链表进行拆分得到两个链表,奇数结点的链表连接起来得到原链表;偶数结点的链表连接起来得到复制的链表。

剑指Offer算法题 27:复杂链表的复制

时间复杂度:O(n);空间复杂度:O(n)

源码

/*
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)
    
{
        //第一步:创建每个节点的影子节点,影子节点跟随在相应的结点的后面,此时只设置指向下一个结点的指针next
        CloneNodes(pHead);
        
        //第二步:根据原链表给影子节点设置对应的特殊指针,此时在第一步的基础上设置特殊指针
        ConnectSiblingNodes(pHead);
        
        //第三步:将长链表拆分成两个链表,奇数结点的为原始链表,偶数结点的为复制出来的目标链表
        return ReconnectNodes(pHead);
    }
    
    //第一步:复制节点
    public void CloneNodes(RandomListNode pHead){
        //假的头结点
        RandomListNode pNode = pHead;
        
        while(pNode != null){
            //pCloned表示克隆的结点
            RandomListNode pCloned = new RandomListNode(pNode.label);
            
            //设置next指针
            pCloned.next = pNode.next;
            
            //这一步设置random指针为null
            pCloned.random = null;
            
            //将克隆的结点接在原结点的后面
            pNode.next = pCloned;
            
            //进行下一次的结点复制操作
            pNode = pCloned.next;
        }
    }
    
    //第二步:补充random指针
    public void ConnectSiblingNodes(RandomListNode pHead){
        //假的头结点
        RandomListNode pNode = pHead;
        
        while(pNode != null){
            //pCloned表示每一个克隆的结点
            RandomListNode pCloned = pNode.next;
            
            if(pNode.random != null){
                //将原结点中有random指针的复制到影子节点中。指向相应的位置的影子节点。
                pCloned.random = pNode.random.next;
            }
            
            //进行下一次random指针的补充操作
            pNode = pCloned.next;
        }
    }
    
    //第三步:拆分链表
    public RandomListNode ReconnectNodes(RandomListNode pHead){
        //假的头结点
        RandomListNode pNode = pHead;
        
        //复制得到的链表的头结点
        RandomListNode pClonedHead = null;
        RandomListNode pClonedNode = null;
        
        //初始时:确定复制的链表的头结点
        if(pNode != null){
            //确定复制的链表的头结点
            pClonedHead = pClonedNode = pNode.next;
            
            //pNode指向复制的链表的头结点的后一个结点
            pNode.next = pClonedNode.next;
            
            //pNode指向复制的链表的头结点的后一个结点
            pNode = pNode.next;
        }
        
        
        //拆分为两个链表,得到复制的新链表
        while(pNode != null){
            //将复制的链表与原链表进行切断操作
            pClonedNode.next = pNode.next;
            pClonedNode = pClonedNode.next;
            pNode.next = pClonedNode.next;
            
            //进行下一次的结点的连接操作
            pNode = pNode.next;
        }
        
        //返回复制的链表的头结点
        return pClonedHead;
    }
}

运行结果

剑指Offer算法题 27:复杂链表的复制


原文始发于微信公众号(AJCoder):剑指Offer算法题 27:复杂链表的复制