Poison

382. Linked List Random Node

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
private final ListNode head;

public Solution(ListNode head) {
this.head = head;
}

public int getRandom() {
int bound = 1, res = 0;

ListNode node = head;
while (node != null) {
if (ThreadLocalRandom.current().nextInt(bound) == 0) {
res = node.val;
}
bound++;
node = node.next;
}

return res;
}
}
Reference

382. Linked List Random Node