题目
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回 结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
思路一
从头遍历遍历原链表，第一次遍历只存储链表的前后关系，不存储他的random节点关系。 第二次再遍历，存储他的random节点，这样的时间复杂度是n平方。
思路二
每遍历一个节点，就将节点信息利用hash进行存储，这样第一次遍历完之后，形成了节点的前后关系， 利用hash获得节点的random关系，利用空间换时间。
思路三
（1）将a-b-c-d变成a-a’-b-b’-c-c’-d-d’；
（2）遍历链表，将复制的节点的random进行复制；
（3）拆分节点，形成两个链表
代码
/*
public class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;
RandomListNode(int label) {
this.label = label;
}
}
*/
public class Solution {
public RandomListNode Clone(RandomListNode pHead)
{
// 头结点为空，直接返回空
if(pHead == null)
return null;
// 复制结点
RandomListNode currentNode = pHead;
while(currentNode != null){
RandomListNode temp = new RandomListNode(currentNode.label);
temp.next = currentNode.next;
currentNode.next = temp;
currentNode = temp.next;
}
// random指正的连接
currentNode = pHead;
while(currentNode != null){
if(currentNode.random != null){
currentNode.next.random = currentNode.random.next;
}
currentNode = currentNode.next.next;
}
//将链表分为两个
RandomListNode newList = pHead.next;
RandomListNode oldList = pHead;
currentNode = pHead.next;
while(currentNode !=null)
{
oldList.next = oldList.next.next;
if(currentNode.next != null){
currentNode.next = currentNode.next.next;
}
oldList = oldList.next;
currentNode = currentNode.next;
}
return newList;
}
}
