|
5 | 5 |
|
6 | 6 | /** |
7 | 7 | * 138. Copy List with Random Pointer |
8 | | - * |
| 8 | + * |
9 | 9 | * A linked list is given such that each node contains an additional random |
10 | 10 | * pointer which could point to any node in the list or null. |
11 | 11 | * Return a deep copy of the list. |
12 | | - * */ |
| 12 | + */ |
13 | 13 |
|
14 | 14 | publicclass_138 { |
15 | | -publicstaticclassSolution1 { |
16 | | -publicNodecopyRandomList(Nodehead) { |
17 | | -/**Key is the original nodes, value is the new nodes we're deep copying to.*/ |
18 | | -Map<Node,Node>map =newHashMap(); |
19 | | -Nodenode =head; |
20 | | - |
21 | | -//loop for the first time: copy the node themselves with only labels |
22 | | -while (node !=null) { |
23 | | -map.put(node,newNode(node.val)); |
24 | | -node =node.next; |
25 | | - } |
26 | | - |
27 | | -//loop for the second time: copy random and next pointers |
28 | | -node =head; |
29 | | -while (node !=null) { |
30 | | -map.get(node).next =map.get(node.next); |
31 | | -map.get(node).random =map.get(node.random); |
32 | | -node =node.next; |
33 | | - } |
34 | | - |
35 | | -returnmap.get(head); |
| 15 | +publicstaticclassSolution1 { |
| 16 | +publicNodecopyRandomList(Nodehead) { |
| 17 | +/**Key is the original nodes, value is the new nodes we're deep copying to.*/ |
| 18 | +Map<Node,Node>map =newHashMap(); |
| 19 | +Nodenode =head; |
| 20 | + |
| 21 | +//loop for the first time: copy the node themselves with only labels |
| 22 | +while (node !=null) { |
| 23 | +map.put(node,newNode(node.val)); |
| 24 | +node =node.next; |
| 25 | + } |
| 26 | + |
| 27 | +//loop for the second time: copy random and next pointers |
| 28 | +node =head; |
| 29 | +while (node !=null) { |
| 30 | +map.get(node).next =map.get(node.next); |
| 31 | +map.get(node).random =map.get(node.random); |
| 32 | +node =node.next; |
| 33 | + } |
| 34 | + |
| 35 | +returnmap.get(head); |
| 36 | + } |
| 37 | + |
| 38 | +// Definition for singly-linked list with a random pointer. |
| 39 | +classNode { |
| 40 | +intval; |
| 41 | + |
| 42 | +Nodenext; |
| 43 | +Noderandom; |
| 44 | + |
| 45 | +Node(intx) { |
| 46 | +this.val =x; |
| 47 | + } |
| 48 | + } |
36 | 49 | } |
37 | | - |
38 | | -// Definition for singly-linked list with a random pointer. |
39 | | -classNode { |
40 | | -intval; |
41 | | - |
42 | | -Nodenext; |
43 | | -Noderandom; |
44 | | - |
45 | | -Node(intx) { |
46 | | -this.val =x; |
47 | | - } |
48 | | - } |
49 | | - } |
50 | 50 | } |