java+HashMap-复杂链表的复制

题目描述
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
解题思路
参考https://www.nowcoder.com/profile/1687题解
完全不懂深复制的含义--将所有的节点以及节点之间的指针复制一遍
重复下两种方法的思路
方法一：
1.复制下所有的节点，并将映射关系用hashmap存储
2.遍历原链表，将指针关系添加到映射的新节点上
3.返回新链表--代码如注释部分
方法二：
1.先遍历，复制所有节点，插入到原节点右侧
2.再遍历，将所有的指针关系添加到新节点上
2.最后遍历实现新旧链表的分离（分离之后原来的链表也得是一个链表）
具体见下图

java代码

/*
public class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}
*/
import java.util.*;
public class Solution {
//     public RandomListNode Clone(RandomListNode pHead)
//     {
//         //使用hashMap来存放随意指针的对应关系
//         HashMap<RandomListNode,RandomListNode> map=new HashMap<>();
//         RandomListNode p=pHead;
//         //先将所有节点复制一遍，并保存映射关系
//         while( p != null){
//             RandomListNode node=new RandomListNode(p.label);
//             map.put(p,node);
//             p=p.next;
//         }
//         //再遍历一遍，处理好指针问题
//         p=pHead;
//         while( p != null){
//             RandomListNode node=map.get(p);//得到新节点
// //             if(p.next==null)  node.next=null;
// //             else node.next=map.get(p.next);
//             node.next=(p.next == null)? null:map.get(p.next);
//             node.random=(p.random == null)? null:map.get(p.random);
//             p=p.next;
//         }
//         //返回新的链表头结点
//         return map.get(pHead);
//     }
    public RandomListNode Clone(RandomListNode pHead)
    {
        if(pHead==null) return null;
        RandomListNode p=pHead;
        //先将所有节点复制一遍，插入在当前节点的右侧
        while( p != null){
            RandomListNode node=new RandomListNode(p.label);
            node.next=p.next;
            p.next=node;
            p=node.next;
        }
        //再遍历一遍，处理好左右指针问题问题
        p=pHead;
        while( p != null){
            if(p.random !=null){
                p.next.random=p.random.next;
            }
            p=p.next.next;
        }
        //分离出复制的链表
        p=pHead;
        RandomListNode ans=p.next;
        while( p != null){
            RandomListNode tmp=p.next;
            p.next=tmp.next;
            if(tmp.next != null){//如果tmp.next为空，则证明走到头了
                tmp.next=tmp.next.next;
            }
            p=p.next;
        }
        return ans;
    }
}