难点：random的深拷贝

• 此题难点在于要深拷贝，新链表中每一个结点都应该指向自己链表中的结点，而不能单纯保存旧表中结点的地址。
• next指向下一个新结点很容易，但random是随机访问，拷贝时就要找到旧random指向的旧结点，对应的新结点是哪个,然后让新结点的random指向这个新结点。
• 新结点在创建时可能指向的random结点还没有被创建，因此这也是不能直接赋值random的原因，链表先链接好再去找random，也得找到新旧结点的对应关系才行。

  方法一：哈希表建立新旧结点间的映射

  public RandomListNode Clone(RandomListNode pHead) {
        if(pHead==null)return pHead;
        Map<RandomListNode,RandomListNode> map = new HashMap<>();
        RandomListNode newHead = new RandomListNode(0);
        RandomListNode cur = pHead,newcur = newHead;
        while(cur!=null){
            RandomListNode clone = new RandomListNode(cur.label);
            //clone.next = cur.next;
            //不能同时拷贝next和random，clone的random还是指向旧表了！
            //clone.random = cur.random;
            //映射，可以通过旧表的radom访问到新表的random
            map.put(cur,clone);//哈希表记录对应新旧节点的映射关系
            //利用newcur把新建的clone连起来
            //clone的next已经ok，只需要填充random
            newcur.next = clone;
            newcur = newcur.next;
            //继续遍历旧链表
            cur = cur.next;
        }
        //哈希表键值对的遍历（key：cur；value：clone）
        for(HashMap.Entry<RandomListNode,RandomListNode> entry:map.entrySet()){
            //entry.getValue().random：新结点clone的random
            //entry.getKey().random：与新结点对应的旧结点cur的random
            //map.get()：获取旧结点random指向的那个新结点！！！
            entry.getValue().random = map.get(entry.getKey().random);
            //等号右侧就阐释了为什么要用哈希表建立映射才能拷贝random！
        }
        return newHead.next;
    }

  方法二：双指针插入旧结点

• 难点：循环停止条件的判断，两链表连接之后，每次指针走两步，最后一个元素必为新结点，所以只有old可能为null，这是循环停止条件（或new.next！=null）

  public RandomListNode Clone(RandomListNode pHead) {
        if(pHead==null)return pHead;
        RandomListNode cur = pHead;
        while(cur!=null){
            RandomListNode clone = new RandomListNode(cur.label);
            clone.next = cur.next;
            cur.next = clone;
            cur = clone.next;
        }
        RandomListNode pre = pHead;
        cur = pHead.next;
        while(pre!=null){
            //循环结束时，应该为：pre=null，cur.next=null
            //因为最后一个元素必为cur，所以cur无法为空，pre可以
            if(pre.random==null)
            {
                cur.random=null;
            }else{
            //若pre的random为空，那么根本访问不到next，会出越界错误
                cur.random = pre.random.next;
            }
            //pre后面还有clone,所以pre.next必定非空
            pre = pre.next.next;
            if(cur.next!=null)
                cur = cur.next.next;
        }
        pre = pHead;
        cur = pHead.next;
        RandomListNode res = cur;
        while(pre != null){
            pre.next = pre.next.next;
            pre = pre.next;
            //若cur的next为空，也意味着pre目前为null
            //这是最后一次循环
            if(cur.next!=null)
                cur.next = cur.next.next;
            cur = cur.next;          
        }
     return res;   
    }