Sponsored
Sponsored
This method involves converting the linked list into an array during the initialization of the Solution object. Once the linked list is stored as an array, we can easily obtain a random node's value by selecting a random index in the array. This guarantees each node has an equal probability of being chosen.
Time Complexity: O(N) for preprocessing, O(1) for getRandom.
Space Complexity: O(N) for storing the list in an array.
1import java.util.ArrayList;
2import java.util.Random;
3
4class ListNode {
5 int val;
6 ListNode next;
7 ListNode(int x) { val = x; }
8}
9
10class Solution {
11 private ArrayList<Integer> values;
12 private Random rand;
13
14 public Solution(ListNode head) {
15 values = new ArrayList<>();
16 rand = new Random();
17 ListNode node = head;
18 while (node != null) {
19 values.add(node.val);
20 node = node.next;
21 }
22 }
23
24 public int getRandom() {
25 int randomIndex = rand.nextInt(values.size());
26 return values.get(randomIndex);
27 }
28}The Java implementation uses an ArrayList to store the values from the linked list. The getRandom method generates a random index, and retrieves the value from this index in the ArrayList, ensuring each node's value is equally probable.
Reservoir Sampling is an efficient algorithm that allows you to randomly select a single item from a stream (or a linked list) of unknown length with all items having an equal probability. You can accomplish this by traversing the linked list node by node, replacing the selected item with decreasing probability.
Time Complexity: O(N) for getRandom.
Space Complexity: O(1).
1
public class ListNode {
public int val;
public ListNode next;
public ListNode(int x) { val = x; }
}
public class Solution {
private ListNode head;
private Random rand;
public Solution(ListNode head) {
this.head = head;
this.rand = new Random();
}
public int GetRandom() {
ListNode node = head;
int reservoir = node.val;
int count = 1;
while (node != null) {
if (rand.Next(count) == 0) {
reservoir = node.val;
}
node = node.next;
count++;
}
return reservoir;
}
}In the C# solution, reservoir sampling is implemented to keep track of one node's value while iterating through the linked list. The strategy grants each node an equal selection probability by adjusting the sampling probability dynamically.