题目描述

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。
要求返回这个链表的深度拷贝。

链表的结点结构如下


 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;
    }
}

用图来解释一下

首先我们把结点表示成这样