-
Notifications
You must be signed in to change notification settings - Fork 0
/
Solution.java
82 lines (75 loc) · 1.99 KB
/
Solution.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
package copylistwithrandompointers;
import java.util.HashMap;
/**
* A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
*
* Return a deep copy of the list.
*
* The Linked List is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:
*
* val: an integer representing Node.val
* random_index: the index of the node (range from 0 to n-1) where random pointer points to, or null if it does not point to any node.
*
*
* Example 1:
*
*
* Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
* Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]
* Example 2:
*
*
* Input: head = [[1,1],[2,1]]
* Output: [[1,1],[2,1]]
* Example 3:
*
*
*
* Input: head = [[3,null],[3,0],[3,null]]
* Output: [[3,null],[3,0],[3,null]]
* Example 4:
*
* Input: head = []
* Output: []
* Explanation: Given linked list is empty (null pointer), so return null.
*
*
* Constraints:
*
* -10000 <= Node.val <= 10000
* Node.random is null or pointing to a node in the linked list.
* Number of Nodes will not exceed 1000.
*/
class Node {
int val;
Node next;
Node random;
Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
class Solution {
HashMap<Node, Node> map = new HashMap<>();
Node copyRandomList(Node head) {
if(head == null)
return null;
if(map.containsKey(head)) {
return map.get(head);
}
else {
Node newNode = new Node(head.val);
map.put(head, newNode);
newNode.next = copyRandomList(head.next);
newNode.random = copyRandomList(head.random);
return newNode;
}
}
}
/*
Success
Details
Runtime: 0 ms, faster than 100.00% of Java online submissions for Copy List with Random Pointer.
Memory Usage: 41.2 MB, less than 5.61% of Java online submissions for Copy List with Random Pointer.
*/