Copy List with Random Pointer

Submission Detail

19 / 19 test cases passed.
 Status:

Accepted
Runtime: 2 ms
Memory Usage: 43.4 MB
Submitted: 0 minutes ago
loading
Runtime Error Message:
Last executed input:
Input:
Output:
Expected:

Accepted Solutions Runtime Distribution

0.0
1.0
2.0
3.0
4.0
5.0
6.0
7.0
8.0
9.0
10.0
75
80
85
90
95
100
105
110
java
Runtime (ms)
Distribution (%)

0
1
2
3
4
5
6
7
8
9
10
80
90
100
110
Zoom area by dragging across this chart

Accepted Solutions Memory Distribution

41500
41750
42000
42250
42500
42750
43000
43250
43500
2
4
6
8
java
You are here!
Your memory usage beats 29.62 % of java submissions.
Memory (KB)
Distribution (%)

41500
41750
42000
42250
42500
42750
43000
43250
43500
5
Zoom area by dragging across this chart

Invite friends to challenge Copy List with Random Pointer

Submitted Code: 0 minutes ago

Language: 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
/*
// Definition for a Node.
class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
*/
class Solution {
public Node copyRandomList(Node head) {
if (head == null)
return null;
Node n = new Node(head.val);
Node nn = new Node(0);
if (head.next != null)
nn.val = head.next.val;
else
nn = null;
n.next = nn;
Node h = head;
head = head.next;
Node c = n;
n = n.next;
// copy list without respect to random
while (head != null) {
Node d = new Node(0);
if (head.next != null)
d.val = head.next.val;
else
d = null;
n.next = d;
head = head.next;
n = n.next;
}
// incorporate random nodes
Node i = c; // copy iterator
Node oi = h; // original iterator
Node orig = h;
while (i != null) {
Node orig_random = orig.random;
Node copy_random = c;
while (oi != orig_random) {
oi = oi.next;
copy_random = copy_random.next;
}
// copy_random now holds the random node
i.random = copy_random;
i = i.next;
orig = orig.next;
oi = h;
}
return c;
}
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Back to problem