forked from DengWangBao/Leetcode-Java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathLinkedListRandomNode.java
More file actions
29 lines (22 loc) · 677 Bytes
/
LinkedListRandomNode.java
File metadata and controls
29 lines (22 loc) · 677 Bytes
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
import java.util.Random;
public class LinkedListRandomNode {
private Random mRandom;
private ListNode mHead;
/** @param head The linked list's head.
Note that the head is guaranteed to be not null, so it contains at least one node. */
public LinkedListRandomNode(ListNode head) {
mRandom = new Random();
mHead = head;
}
/** Returns a random node's value. */
public int getRandom() {
int count = 0;
int value = -1;
for (ListNode p = mHead; p != null; p = p.next) {
if (mRandom.nextInt(++count) == 0) {
value = p.val;
}
}
return value;
}
}