一、问题描述
1、描述
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
2、方法体
public RandomListNode Clone(RandomListNode pHead) {
}
二、思路
最开始我的思路是从头结点开始复制，当复制出一条链表后加入random结点。但是存在的问题是，每次遍历一个结点，都要将链表重新遍历一次才可以找到复制的random结点，增加了时间复杂度。
后来考虑，所谓查找random结点，可以用一个map存储，每次找到对应的映射就可以。
三、存在问题及解决
代码很顺利
但是，在题干有一句话，如果返回结果存在对参数的引用，那么返回值为空。在最开始我提交的代码运行结果为空，重新检查代码发现，在复制链表的next结点时，我写的代码如下：
map.get(p2).next = p2.next;
这条代码相当于将输入参数的p2.next传入，也就是所谓的参数的引用。
正确的做法应该是找到复制的结点，然后赋值。
四、代码
具体实现代码如下：
public RandomListNode Clone(RandomListNode pHead) {
//如果pHead为null，返回result
if (pHead == null) {
return null;
}
//将p1拷贝到map中，利用p2将map中的数据random进行对应
RandomListNode p1 = pHead;
RandomListNode p2 = pHead;
HashMap<RandomListNode, RandomListNode> map = new HashMap<>();
while (p1 != null) {
map.put(p1, new RandomListNode(p1.label));
p1 = p1.next;
}
while (p2 != null) {
map.get(p2).next = map.get(p2.next);
map.get(p2).random = map.get(p2.random);
p2 = p2.next;
}
return map.get(pHead);
}