题解 | #复杂链表复制#

/*
public class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}
*/
import java.util.* ;
public class Solution {
    public RandomListNode Clone(RandomListNode pHead) {
        if(pHead == null) {
            return null ;
        }
        RandomListNode c = pHead ;
        RandomListNode pre = new RandomListNode(0) ;
        RandomListNode n = pre ;
                //思路就是：将 1.旧结点：新节点 存入 map
                                2.再次遍历旧链表与新链表，要找到新节点对应的random，就是旧结点的random对应的新节点
        //旧结点：新结点
        HashMap<RandomListNode , RandomListNode> map = new HashMap<>() ;
        while(c != null) {
            RandomListNode newNode = new RandomListNode(c.label) ; 
            map.put(c,newNode) ;
            n.next = newNode ;
            n = n.next ;
            c = c.next ;
        }
        c = pHead ;
        n = pre.next ;
        while(c != null) {
            n.random = map.get(c.random);
            n = n.next ;
            c = c.next ;
        }
        return pre.next ;
    }
}