本题考察的是链表的插入删除操作
题目描述
给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。
要求返回这个链表的深度拷贝。
链表的结点结构如下
class RandomListNode {
int label;
RandomListNode next, random;
RandomListNode(int x) { this.label = x; }
};
题目思考
这道题比常规的链表复制多了一个随机指针random。按照常规的解法，我们可以用一个HashMap<RandomListNode ,RandomListNode >维护从原始结点到复制结点的映射，这样我们在复制链表的时候不会重复创建结点。
但是，在看了大神的代码后，我惊呆了，原来还可以这么做。详细解析往下看
代码1
java 7ms
public class Solution {
public RandomListNode copyRandomList(RandomListNode head) {
if(head==null)
return null;
Map<RandomListNode,RandomListNode> map=new HashMap<RandomListNode,RandomListNode>(); //创建从源结点到复制结点的映射
RandomListNode myHead = new RandomListNode(head.label),cur=head,myCur=myHead;
map.put(cur,myCur);//先把头结点放到map中
while(cur!=null){ //首先不管random指针，只按照next指针复制链表，把每一组映射添加到map中
myCur.next=map.get(cur.next);
if(myCur.next==null&&cur.next!=null){
myCur.next=new RandomListNode(cur.next.label);
map.put(cur.next,myCur.next);
}
myCur=myCur.next;
cur=cur.next;
}
cur=head;
myCur=myHead;
while(cur!=null){ //连接random指针，把每一组映射添加到map中
myCur.random=map.get(cur.random);
if(myCur.random==null&&cur.random!=null){
myCur.random=new RandomListNode(cur.random.label);
map.put(cur.random,myCur.random);
}
myCur=myCur.next;
cur=cur.next;
}
return myHead;
}
}
这个代码思路很直观，首先根据next指针复制所有结点，练成一条链，并把源结点作为key,复制后的结点作为value放到map中。然后再连接所有的random指针，根据源结点从map中找到复制后的结点添加到map指针中。
下面是我复制大神的代码
代码2
java 1ms
public class Solution {
public RandomListNode copyRandomList(RandomListNode head) {
if(head==null)
return null;
RandomListNode cur=head;
while(cur!=null){
RandomListNode temp=new RandomListNode(cur.label); //复制结点
temp.next=cur.next;//把复制后的结点放到源结点的next指针上
cur.next=temp;
cur=cur.next.next;
}
cur=head;
while(cur!=null){ //连接所有复制后结点的random指针
cur.next.random= cur.random==null? null:cur.random.next;
cur=cur.next.next;
}
cur=head;
RandomListNode myHead=cur.next;
RandomListNode myCur=myHead;
while(cur!=null){ //删除源结点和复制后结点之间的连接
cur.next=myCur.next;
cur=cur.next;
myCur.next=cur==null? null:cur.next;
myCur=myCur.next;
}
return myHead;
}
}
用图来解释一下
首先我们把结点表示成这样
结点表示
然后我们假设需要复制的链表是这样的
需要复制的链表
首先我们复制结点，并把复制后的结点放到源结点的next指针上
复制结点，连接next指针
然后连接复制后结点的random指针
连接random指针
最后断开源结点和复制后结点的连接，连接复制后结点的next指针
重连random
这样就完成了链表的复制
