剑指offer-25-复杂链表的复制

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

这道题目刚开始读起来没有思路，最后只能用比较笨拙的方法来实现，用map保留过曾经访问过的值。只是在写代码的过程中原始链表和新链表的指针弄反了，以至于到最后报空指针错误，哎，以后变量的命名还是要规范化一点比较好

//下面那段代码思维太混乱了，大家不要参考，如果要用map解决此题，看这段代码就好
import java.util.HashMap;
public class Solution {
    public RandomListNode Clone(RandomListNode pHead)
    {
        HashMap<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
        RandomListNode p = pHead;
        //第一次遍历 新建立节点
        while(p != null){
            RandomListNode newNode = new RandomListNode(p.label);
            map.put(p, newNode);
            p = p.next;
        }
        //第二次遍历 赋值映射关系
        p = pHead;
        while(p != null){
            RandomListNode node = map.get(p);
            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);

    }
}

整体思路还是想的比较简单：用map保存旧节点和新节点之间的映射关系，如果节点已经存在那么使用存在的节点即可，如果不存在那么需要新开辟节点并存储他们之间的映射关系

import java.util.Map;
import java.util.HashMap;
public class Solution {
    public RandomListNode Clone(RandomListNode pHead)
    {
        if(pHead == null)return null;
        RandomListNode newHead = null;
        RandomListNode p = pHead;
        RandomListNode q = null;
        Map<RandomListNode, RandomListNode> map = new HashMap<>();
        while(p != null){
            if(newHead == null){
                newHead = new RandomListNode(pHead.label);
                q = newHead;
                map.put(pHead, newHead);
            }else{