138. 复制带随机指针的链表

class Solution {
    public Node copyRandomList(Node head) {
        if(head==null){
            return null;
        }
        //使用HashMap方法构造映射  原节点,新节点
        Map<Node,Node> map=new HashMap();
        Node temp=head; //操作他
        while(temp!=null){
            Node clone=new Node(temp.val,null,null);//构建新节点  下一个节点是空 random也是空
            //构建新节点映射
            map.put(temp,clone);//旧街点  新节点
            temp=temp.next;
        }
        //构建新节点的random 和 next
        temp=head;//恢复到初始位置
        while(temp!=null){
            //新节点的next= 新节点的下一个节点
            map.get(temp).next=map.get(temp.next);
            map.get(temp).random=map.get(temp.random);
            temp=temp.next;
        }

        //返回新节点
        return map.get(head);

    }
}