输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
第一种方法：使用map存放原节点和其复制节点。然后再给复制节点的next/random指针初始化。初始化时，原节点p，p的复制节点的next=p.next的复制节点
见代码：
public RandomListNode copyRandomList(RandomListNode head) {
if(head==null) return null;
//map存放原节点和复制节点
Map<RandomListNode,RandomListNode> map=new HashMap<RandomListNode,RandomListNode>();
RandomListNode p=head;
//将所有节点及其复制节点放到hashmap中
while(p!=null){
map.put(p,new RandomListNode(p.label));
p=p.next;
}
//给复制节点的指针赋值
p=head;
while(p!=null){
map.get(p).next=map.get(p.next);//p的复制节点的next等于p.next的复制节点。
map.get(p).random=map.get(p.random);
p=p.next;
}
return map.get(head);
}
第二种方法：
分三步：
1、根据next指针，复制原链表，在原链表中复制，将所有节点复制到原节点后面（如a->b->c复制成a->a'->b->b'->c->c'）
2、根据链表的random指针，在新链表中初始化复制节点的random指针。.next.random=.random.next
3、从复制后的链表中拆分出新的复制链表返回
如果只有一个next指针，则省略上面第2步
public RandomListNode copyRandomList(RandomListNode head) {
if(head==null) return null;
RandomListNode pCur=head;//用于遍历
//第一步，根据next指针复制如a->b->c复制成a->a'->b->b'->c->c'
while(pCur!=null){
RandomListNode node=new RandomListNode(pCur.label);
node.next=pCur.next;
pCur.next=node;
pCur=node.next;
}
pCur=head;
//第二步，初始化复制后节点的random指针
while(pCur!=null){
if(pCur.random!=null){ //不用判断p.next是否为空，因为p不为空，p.next是复制节点，肯定不为空
pCur.next.random=pCur.random.next;//要指向p.random的复制节点，所以有.next
}
pCur=pCur.next.next;
}
//第三步，拆分
RandomListNode phead=head.next;
RandomListNode p=phead;
pCur=head;
while(pCur!=null){
pCur.next=pCur.next.next;
if(p.next!=null){
p.next=p.next.next;
}
p=p.next;
pCur=pCur.next;
}
return phead;
}
可以看出，上面第一种方法简单很多。