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.
1typedef struct ListNode {
2 int val;
3 struct ListNode *next;
4} ListNode;
5
6typedef struct {
7 int *values;
8 int size;
9} Solution;
10
11Solution* solutionCreate(ListNode* head) {
12 Solution* obj = (Solution*) malloc(sizeof(Solution));
13 obj->size = 0;
14 ListNode* temp = head;
15 while (temp) {
16 obj->size++;
17 temp = temp->next;
18 }
19 obj->values = (int *)malloc(obj->size * sizeof(int));
20 temp = head;
21 int index = 0;
22 while (temp) {
23 obj->values[index++] = temp->val;
24 temp = temp->next;
25 }
26 return obj;
27}
28
29int solutionGetRandom(Solution* obj) {
30 int randomIndex = rand() % obj->size;
31 return obj->values[randomIndex];
32}
33
34void solutionFree(Solution* obj) {
35 free(obj->values);
36 free(obj);
37}In this solution, we first traverse the linked list to determine its size. We then allocate an array to hold all node values. A second traversal fills the array with the linked list's values. The getRandom function simply selects a random index from the array using the rand() function.
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).
1import
Utilizing Python's random number generator, this solution efficiently picks a random node from the linked list using reservoir sampling, where each item maintains equal likelihood of being selected throughout.