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.
1using System;
2using System.Collections.Generic;
3
4public class ListNode {
5 public int val;
6 public ListNode next;
7 public ListNode(int x) { val = x; }
8}
9
10public class Solution {
11 private List<int> values = new List<int>();
12 private Random rand = new Random();
13
14 public Solution(ListNode head) {
15 while (head != null) {
16 values.Add(head.val);
17 head = head.next;
18 }
19 }
20
21 public int GetRandom() {
22 int randomIndex = rand.Next(values.Count);
23 return values[randomIndex];
24 }
25}The C# implementation stores all node values in a List<int>. The GetRandom method then selects a random index using Random.Next() to ensure uniform distribution among the list's nodes.
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
This C solution applies reservoir sampling to randomly select a node from the linked list. For each node, with probability 1/count, the current node value is chosen as the reservoir value, allowing us to accomplish this in one pass with constant space.