Problem
Given a singly linked list, return a random node’s value from the linked list. Each node must have the same probability of being chosen.
Implement the Solution
class:
Solution(ListNode head)
Initializes the object with the head of the singly-linked listhead
.int getRandom()
Chooses a node randomly from the list and returns its value. All the nodes of the list should be equally likely to be chosen.
Examples
Example 1:
graph LR; 1 --> 2 --> 3
Input
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1, 2, 3]], [], [], [], [], [
Output
[null, 1, 3, 2, 2, 3]
Explanation
Solution solution = new Solution([1, 2, 3]);
solution.getRandom(); // return 1
solution.getRandom(); // return 3
solution.getRandom(); // return 2
solution.getRandom(); // return 2
solution.getRandom(); // return 3
// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.
Constraints
- The number of nodes in the linked list will be in the range
[1, 104]
. -104 <= Node.val <= 104
- At most
104
calls will be made togetRandom
.
Solution
Method 1 - Using List Size
Use inbuilt random function to pickup the random value.
Code
Java
class Solution {
private final ListNode head;
private int size;
public Solution(ListNode head) {
this.head = head;
size = 0;
ListNode current = head;
while (current != null) {
current = current.next;
size++;
}
this.size = size;
}
public int getRandom() {
int randInt = (int)(Math.random() * size);
ListNode curr = head;
while (randInt > 0 && curr.next != null) {
curr = curr.next;
randInt--;
}
return curr.val;
}
}
Complexity
- ⏰ Time complexity:
O(n)
for construction andO(n)
for get random, wheren
is length of linked list - 🧺 Space complexity:
O(n)
for storing n values in list
Method 4 - Using Reservoir Sampling and without Extra Space 🏆
We can use Reservoir Sampling Explained for k=1
.
Read more about . Lets discuss how it applies here:
- lets says if the values are coming as
1, 2, 3 ..
- on
1
then we have1
only choice to select :1
- on
2
then out of two elements, we need to select1
, then new item should be given1/2
chance - so any random number that comes less than or equal to
1/2
then select :2
- on
3
then out of three elements, we need to select1
, then new item should be given1/3
chance, others will have2/3
probability because they already exists with more probabilty - so select :
3
if random number comes between0 < random <= 1/3
Code
Java
Using Arraylist
public class Solution {
private ListNode head;
private Random rand;
/** Note that the head is guaranteed to be not null, so it contains at least one node. */
public Solution(ListNode head) {
this.head = head;
this.rand = new Random();
}
/** Returns a random node's value. */
public int getRandom() {
int k = 1;
ListNode node = this.head;
int res = node.val;
int i = 0;
ArrayList<Integer> reservoir = new ArrayList<Integer>();
while (i < k && node != null) {
reservoir.add(node.val);
node = node.next;
i++;
}
i++; // i == k => i == k+1
while (node != null) {
if (rand.nextInt(i) < k) {
reservoir.set(rand.nextInt(k), node.val);
}
i++;
node = node.next;
}
return reservoir.get(0);// or return reservoir when k > 1;
}
}
Code Using Math.random()
class Solution {
ListNode node;
public Solution(ListNode head) {
//store the head in node
node = head;
}
public int getRandom() {
//running index, i
int count = 1;
//our selection
ListNode candidate = null;
// curr assigned with the head of the node
ListNode curr = node;
//loop through all the nodes
while (curr != null) {
//pick random and check if the value is<or<= 1/i
if (Math.random()<= 1.0 / count) {
candidate = curr;
}
count += 1;
curr = curr.next;
}
return candidate.val;
}
}
Code Using rand.nextInt()
we can also use rand.nextInt()
and count
.
public class Solution {
ListNode head;
public Solution(ListNode h) {
head = h;
}
public int getRandom() {
Random rand = new Random();
int count = 0;
ListNode curr = head;
ListNode candidate = head;
// traverse till end of list
while (true) {
if (curr == null) {
break;
}
if (rand.nextInt(count + 1) == count) {
candidate = curr;
}
curr = curr.next;
count++;
}
return candidate.val;
}
}