leetcode 138. Copy List with Random Pointer

Seawolf

/*
// Definition for a Node.
class Node {
    public int val;
    public Node next;
    public Node random;

    public Node() {}

    public Node(int _val,Node _next,Node _random) {
        val = _val;
        next = _next;
        random = _random;
    }
};
*/
class Solution {
    
    public Node copyRandomList(Node head) {
        
        HashMap<Node,Integer> map = new HashMap<Node,Integer>();
        
        ArrayList<Node> lst = new ArrayList<Node>();
        
        Node ptr = head;
        
        int i = 0;
        
        while(ptr != null){
            
            map.put(ptr,i);
            
            lst.add(new Node(ptr.val,ptr.next,ptr.random));
            
            i++;
            
            ptr = ptr.next;
            
        }
        
        lst.add(null);
        
        i = 0;
        
        ptr = head;
        
        while(ptr != null){
            
            lst.get(i).next = lst.get(i+1);
            
            if(ptr.random != null){
                
                int id = map.get(ptr.random);
                
                lst.get(i).random = lst.get(id);
            }
            
            ptr = ptr.next;
            
            i++;
            
        }
    
        
        return lst.get(0);
        
    }
}