复杂链表的复制

考点：链表 分解让复杂问题简单化

题目描述

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的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)
    {        
    }
}

解题一

1.思路
参考：
第一步：让仍然是根据原始链表的每个结点N创建对应的N'。不过我们把N’链接在N的后面。

image.png

第二步：设置复制出来的结点的m_pSibling。原始链表上的A的m_pSibling指向结点C，那么其对应复制出来的A’是A的m_pNext指向的结点，同样C’也是C的m_pNext指向的结点。即A' = A.next，A'.m_pSibling = A.m_pSibling.next；故像这样就可以把每个结点的m_pSibling设置完毕。

image.png

第三步：将这个长链表拆分成两个链表：把奇数位置的结点用m_pNext链接起来就是原始链表，把偶数位置的结点用m_pNext链接起来就是复制出来的链表。

image.png

原文链接：https://blog.csdn.net/u013132035/article/details/80625419

2.代码

/*
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 currentNode=pHead;
        //1、复制链表
        //复制每个结点，将其复制后的结点插到原结点的后面
        while(currentNode!=null){
             //创建源节点相同的复制结点
            RandomListNode cloneNode=new RandomListNode(currentNode.label);
            RandomListNode nextNode=currentNode.next;
            currentNode.next=cloneNode;
            cloneNode.next=nextNode;
            currentNode=nextNode;
        }
        //2、复制链表的复杂指针
        //定义一个指针，指向头结点
        currentNode=pHead;
        //重新遍历链表，复制老结点的随机指针给新链表
        while(currentNode!=null){
            //此处需要判断当前结点的任意指针是否为空
            currentNode.next.random=currentNode.random==null?null:currentNode.random.next;
            currentNode=currentNode.next.next;
        }
        
        //3、将复制到链表与原来的链表拆开
        //定义一个指针指向复制链表的头结点
        currentNode=pHead;
        RandomListNode pCloneNode=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 pCloneNode;
    }    
}

3.时间复杂度为0(n)
空间复杂度为O(n)

解题二

1.思路
1）创建一个map 遍历链表将每个结点 和复制当前结点的结点 构成一个key 和value放进map中
2）再次遍历链表 将每个结点作为key去查找map中的val 即复制的结点 它的next域就是 当前结点的next在map中的val 他的random域就是 当前结点的random在map中的val
这种方法的时间复杂度为0(n) 额外空间复杂度为O(n)
2.代码

import java.util.HashMap;
/*
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 pHead;
        }
        //定义两个指针p1、p2，让他们分别指向头结点
        RandomListNode p1=pHead;
        RandomListNode p2=pHead;
        //一个Node对应源链表，另一个Node对应复制的链表
        HashMap<RandomListNode,RandomListNode> map=new HashMap<>();
        //先将节点全部复制
        while(p1!=null){
            map.put(p1,new RandomListNode(p1.label));
            p1=p1.next;
        }
        while(p2!=null){
            //key对应源表的每一个节点，value对应复制链表的每一个节点
            if(p2.next!=null){
                map.get(p2).next=map.get(p2.next);
            }else {
               map.get(p2).next=null;
            }
             map.get(p2).random=map.get(p2.random);
            p2=p2.next;
        }
        return map.get(pHead);
    }
}

3.时间复杂度为0(n)
空间复杂度为O(1)