leetcode 138. Copy List with Random Pointer

Seawolf

1. /*
   
2. // Definition for a Node.
   
3. class Node {
   
4.     public int val;
   
5.     public Node next;
   
6.     public Node random;
   
7. 
   
8.     public Node() {}
   
9. 
   
10.     public Node(int _val,Node _next,Node _random) {
    
11.         val = _val;
    
12.         next = _next;
    
13.         random = _random;
    
14.     }
    
15. };
    
16. */
    
17. class Solution {
    
18.    
    
19.     public Node copyRandomList(Node head) {
    
20.         
    
21.         HashMap<Node,Integer> map = new HashMap<Node,Integer>();
    
22.         
    
23.         ArrayList<Node> lst = new ArrayList<Node>();
    
24.         
    
25.         Node ptr = head;
    
26.         
    
27.         int i = 0;
    
28.         
    
29.         while(ptr != null){
    
30.             
    
31.             map.put(ptr,i);
    
32.             
    
33.             lst.add(new Node(ptr.val,ptr.next,ptr.random));
    
34.             
    
35.             i++;
    
36.             
    
37.             ptr = ptr.next;
    
38.             
    
39.         }
    
40.         
    
41.         lst.add(null);
    
42.         
    
43.         i = 0;
    
44.         
    
45.         ptr = head;
    
46.         
    
47.         while(ptr != null){
    
48.             
    
49.             lst.get(i).next = lst.get(i+1);
    
50.             
    
51.             if(ptr.random != null){
    
52.                
    
53.                 int id = map.get(ptr.random);
    
54.                
    
55.                 lst.get(i).random = lst.get(id);
    
56.             }
    
57.             
    
58.             ptr = ptr.next;
    
59.             
    
60.             i++;
    
61.             
    
62.         }
    
63.    
    
64.         
    
65.         return lst.get(0);
    
66.         
    
67.     }
    
68. }

复制代码