复杂链表复制问题

题目描述：

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

解题思路：

对于深拷贝：利用HashMap来存放节点以及节点值：即遍历链表，然后将其节点以及节点值put进HashMap；然后通过移动链表将获取的节点复制到另一个链表中

public class Solution {
    public RandomListNode Clone(RandomListNode pHead)
    {
        if(pHead==null){
            return null;
        }
        //创建一个node节点用来存放返回拷贝后的节点,需要new()
        RandomListNode node=new RandomListNode(pHead.label);
        //当前节点链表
        RandomListNode current=pHead;
        //拷贝后节点链表
        RandomListNode copyCurrent=node;
        //用来存放每个节点及对应的节点值
        HashMap<RandomListNode,RandomListNode> map=new HashMap<>();
        //遍历当前链表，并将数据存放到map中
        while(pHead!=null){
            map.put(pHead,new RandomListNode(pHead.label));
            pHead=pHead.next;
        }
        //通过移动当前链表进行深拷贝
        while(current!=null){
            copyCurrent.next=map.get(current.next);
            copyCurrent.random=map.get(current.random);
            current=current.next;
            copyCurrent=copyCurrent.next;
        }
        //返回深拷贝后的头节点
        return node;
    }
}

为什么不返回copyCurrent,是因为copyCurrent这个在移动，最后会指向null
拓展学习：
首先来了解一下内存分区：

其次我们需要了解一下基本类型与引用类型得区别：

基本类型：

就是值类型，即变量所对应得内存区域存储的是值

引用类型：

就是地址类型，真正的数据存储在地址对应的内存区域里面

浅拷贝：

只是将数据中所有的数据引用下来，依旧指向同一个存放地址，拷贝之后的数据修改之后，也会影响到原数据的中的对象数据

深拷贝：（引用类型需要new()）

将数据中所有的数据拷贝下来，对拷贝之后的数据进行修改不会影响到原数据