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

最暴力的方法：首先利用next指针将复制的节点串起来，然后在每一个节点处，去寻找random指针指向哪，然后在复制的链表中找到对应的节点。因为每次去寻找指针都会从头移动O(n)，而又有n个节点，因此时间复杂度是O(n^2)
有两种改进方式。
改进1：一种是空间换时间，在复制节点时，用map保存旧节点和新节点之间的映射关系。然后分别复制next和random，一共两轮循环，所以时间复杂度是O(n)，空间复杂度是O(n)

import java.util.HashMap;
public class Solution {
    public RandomListNode Clone(RandomListNode pHead)
    {
        if (pHead == null) {
            return pHead;
        }
        RandomListNode p1 = pHead; //p1是指向旧链表的指针，将新旧节点对应
        RandomListNode p2 = pHead; //p2是指向新链表的指针
        HashMap<RandomListNode, RandomListNode> map = new HashMap<>();
        while (p1 != null) {
//存放的是p1节点和一个新节点，这个新节点的值和p1的值相同
//通俗来看，这一步是将节点复制，但是没有串起来（复制好了每一个颗糖葫芦，但是没串到竹签上）
            RandomListNode clone = new RandomListNode(p1.label);
            map.put(p1, clone);
            p1 = p1.next;
        }
        while (p2 != null) {//p2在原链表上移动
//map.get(p2)通过键值对，拿到了新链表在p2位置的节点应该是哪一个
//map.get(p2).next= 表示这个新链表的p2位置节点的下一个节点应该指向？
//map.get(p2.next) 表示拿到原链表p2位置节点指向的下一个节点
//这个赋值通俗来就是，根据原来的糖葫芦顺序，把复制的每一颗的糖葫芦依葫芦画瓢的串起来
            if (p2.next != null) {
                map.get(p2).next = map.get(p2.next);
            } else {
                map.get(p2).next = null;
            }
//这里就是进行random指针的复制，这里的random和next的复制顺序可以交换，p2=p2.next必须在最后
            map.get(p2).random = map.get(p2.random);
            p2 = p2.next;
        }
        return map.get(pHead);
    }
}

改进2：不用O(n)的空间复杂度，依旧实现时间复杂度是O(n)
来自Cyc20***佬的图
图片说明 

public RandomListNode Clone(RandomListNode pHead) {
    if (pHead == null)
        return null;
    // 插入新节点（插入节点的写法），同时建立了next连接
    RandomListNode cur = pHead;
    while (cur != null) {
        RandomListNode clone = new RandomListNode(cur.label);
        clone.next = cur.next;
        cur.next = clone;
        cur = clone.next;
    }
    // 建立 random 链接（从头开始）
    cur = pHead;
    while (cur != null) {
        RandomListNode clone = cur.next;
        if (cur.random != null)
            clone.random = cur.random.next;
        cur = clone.next;
    }
    // 拆分
//拆分的细节需要注意   a->a1->b->b1->c->c1
    cur = pHead;//当前指针指向a
    RandomListNode pCloneHead = pHead.next;//一个指向a1的指针
    while (cur.next != null) {//第一个whlie的功能仅仅是a->a1变成a->b。
        RandomListNode next = cur.next;//next是指向a1的指针
        cur.next = next.next;//a将会与b连接（a不再指向a1，而是b了，就这一处改动）
        cur = next;//指针指向a1，以便下次进行a1到b的拆分（完成了一次拆分）
    }
//每一次whlie，都会改变一次连接（改变一个箭头指向，而不是多个箭头）。
//第一次将a与b连接，第二次将a1与b1连接，第三次是将b与c连接....
    return pCloneHead;
}