/*
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 ;
         }
        //正向映射
        HashMap<RandomListNode,RandomListNode> map1 = new HashMap<>() ;
        //反向映射
        HashMap<RandomListNode,RandomListNode> map2 = new HashMap<>() ;
        //新链表的头结点
        RandomListNode ret_pre = new RandomListNode(Integer.MIN_VALUE) ;
        //新链表指针
        RandomListNode ret_cur = ret_pre ;
        //原链表指针
        RandomListNode cur = pHead ;
        while(cur != null) {
            ret_cur.next = new RandomListNode(cur.label) ;
            ret_cur = ret_cur.next ;
            map1.put(ret_cur,cur) ;
            map2.put(cur , ret_cur) ;
            cur = cur.next ;
        }
        ret_cur = ret_pre.next ;
        //开始给新链表的 random指针 赋值
        while(ret_cur != null) {
            ret_cur.random = map2.get(map1.get(ret_cur).random) ;
            ret_cur = ret_cur.next ;
        }
        return ret_pre.next ;
    }
}