题目描述：
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
分析：
复杂链表是指一个链表有若干个节点，每个节点都有一个数据域用来存放数据，还有两个指针域，其中一个指向下一个节点，另一个随机指向当前复杂链表中的任意一个节点或者空节点。
故而，复杂链表的复制重点在于random指针的指向
思路一：先复制链表上每个节点，通过next指针串联起来，然后再设置每个节点的random指针。假设原始链表中节点N的random指针指向节点S，那么就需要从头到尾遍历查找节点S，若从头结点到S需要经过M步，那么复制链表的N‘节点的random指针即指向距离头结点M步的节点。
时间复杂度：o(n^2)
思路二：通过空间换取时间，将原始链表和复制链表的结点通过哈希表对应起来，这样查找的时间就从O(N)变为O(1)。具体如下：
复制原始链表上的每个结点N创建N'，然后把这些创建出来的结点用pNext连接起来。同时把<N,N'>的配对信息方法一个哈希表中；然后设置复制链表中的每个结点的pSibling指针，如果原始链表中结点N的pSibling指向结点S，那么在复制链表中，对应的N'应该指向S'。
时间复杂度：O(N)
思路三：在不使用辅助空间的情况下实现O(N)的时间效率。
第一步：根据原始链表的每个结点N创建对应的N'，然后将N‘通过pNext接到N的后面；
第二步：设置复制出来的结点的pSibling。假设原始链表上的N的pSibling指向结点S，那么其对应复制出来的N'是N->pNext指向的结点，同样S'也是结点S->pNext指向的结点。
第三步：把长链表拆分成两个链表，把奇数位置的结点用pNext连接起来的就是原始链表，把偶数位置的结点通过pNext连接起来的就是复制链表。
解答：
这里采用第三种方法解答，第三种方法有些难想到，但是写成代码，逻辑很清晰。而且没有使用额外的辅助空间，时间复杂度也控制在O（n），是最好的解法。（这种解法相当于一共从头到尾的遍历了三次链表，耗时3*n,故而时间复杂度为O(N)。）
/*
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;
createDoubleNode(pHead);
connectRandomNode(pHead);
return ReconnectNodes(pHead);
}
//复制节点
private void createDoubleNode(RandomListNode pHead){
RandomListNode tmpNode = pHead;
while(tmpNode!=null){
RandomListNode node = new RandomListNode(tmpNode.label);
node.next = tmpNode.next;
tmpNode.next = node;
tmpNode = node.next;
}
}
//连接random节点
private void connectRandomNode(RandomListNode pHead){
RandomListNode tmp = pHead;
while(tmp!=null){
if(tmp.random!=null){
RandomListNode node = tmp.next;
node.random = tmp.random.next;
tmp = node.next;
}else{
tmp = tmp.next.next;
}
}
}
//把合在一起的链表拆分成两个
private RandomListNode ReconnectNodes(RandomListNode pHead){
if(pHead==null) return null;
RandomListNode tmp = pHead;
RandomListNode newHead = pHead.next;
while(tmp!=null){
RandomListNode node = tmp.next;
tmp.next = node.next;
if(node.next!=null){
node.next = node.next.next;
}else{
node.next = null;
}
tmp = tmp.next;
}
return newHead;
}
}
