JZ25 复杂链表的复制，三种做法

三种做法。

方法一：先存后连

第一遍先从头到尾都把next连好，并且把原链表节点和新链表节点一一对应存进HashMap中。再对照HashMap一一连好Random。
（显然也可以首先存好节点对，最后一起连next和Random。）

import java.util.*;
public class Solution {
    public RandomListNode Clone(RandomListNode pHead){
        if(pHead==null) return null;
        RandomListNode root=new RandomListNode(pHead.label);
        RandomListNode curr=root;
        Map<RandomListNode, RandomListNode> map=new HashMap<>();
        map.put(pHead,curr);
        while(pHead.next!=null){
            RandomListNode next=new RandomListNode(pHead.next.label);
            curr.next=next;
            curr=next;
            pHead=pHead.next;
            map.put(pHead,curr);
        }
        for(RandomListNode i:map.keySet()){
            RandomListNode r=map.get(i);
            r.random=map.get(i.random);
        }
        return root;
    }
}

方法二：边连边存

连之前先检查对应的next，random节点是不是已经被新建出来了，能连好的next，random就连好，没有就新建再存。

import java.util.*;
public class Solution {
    public RandomListNode Clone(RandomListNode pHead){
        if(pHead==null) return null;
        RandomListNode root=new RandomListNode(pHead.label);
        RandomListNode curr=root;
        Map<RandomListNode, RandomListNode> map=new HashMap<>();
        map.put(pHead,curr);
        while(pHead.next!=null){
            RandomListNode next=curr;
            if(!map.containsKey(pHead.next))
                next=new RandomListNode(pHead.next.label);
            else
                next=map.get(pHead.next);
            curr.next=next;
            if(!map.containsKey(pHead.random)){
                RandomListNode r=pHead.random==null? null:
                    new RandomListNode(pHead.random.label);
                curr.random=r;
                map.put(pHead.random, r);
            }
            else
                curr.random=map.get(pHead.random);
            curr=curr.next;
            pHead=pHead.next;
        }
        curr.random=map.get(pHead.random);
        return root;
    }
}

方法三：“套娃做法”

就是前排里面的做法了。这个想法可以由HashMap推广得到。
为什么我们要建立HashMap呢？因为我们想要建立起原链表节点和新链表节点的一一对应。
那么直接在原链表节点后插入新链表节点不就好了嘛！
记得之后要“解套”，再变回两个单独的链表！

public class Solution {
    public RandomListNode Clone(RandomListNode pHead){
        if(pHead==null) return null;
        RandomListNode head=pHead;
        while(pHead!=null){
            RandomListNode curr=new RandomListNode(pHead.label);
            curr.next=pHead.next;
            pHead.next=curr;
            pHead=pHead.next.next;
        }
        pHead=head;
        while(pHead!=null){
            pHead.next.random=pHead.random==null? null:pHead.random.next;
            pHead=pHead.next.next;
        }
        pHead=head;
        RandomListNode qHead=head.next;
        RandomListNode ans=head.next;
        while(pHead!=null){
            if(qHead!=null) {pHead.next=qHead.next; pHead=pHead.next;}
            if(pHead!=null) {qHead.next=pHead.next; qHead=qHead.next;}          
        }
        return ans;
    }
}

方法二和方法三中需要尤其注意，random可以为null，所以选择条件不能丢！