Welcome to Subscribe On Youtube
382. Linked List Random Node
Description
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 singlylinked 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.
Example 1:
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, 10^{4}]
. 10^{4} <= Node.val <= 10^{4}
 At most
10^{4}
calls will be made togetRandom
.
Follow up:
 What if the linked list is extremely large and its length is unknown to you?
 Could you solve this efficiently without using extra space?
Solutions
The challenge is to implement the solution in a way that each node has an equal probability of being chosen, given that the size of the linked list is unknown
or may not fit into memory
(thus, not allowing for a simple arraybased solution where one could just pick a random index).
Reservoir Sampling
This solution uses a technique called Reservoir Sampling. It’s a fantastic strategy for sampling from a population of unknown size with uniform distribution. The idea is to iterate through each element (or node, in this case), deciding whether to keep it as the current answer or not, until you’ve seen all elements.
Why Reservoir Sampling Works for Large or Unknown Length Lists:

Unknown Length: The beauty of Reservoir Sampling is that it doesn’t require knowledge of the population size (or the linked list’s length) beforehand. It processes each item (or node) one at a time and decides whether to include it in the sample (in this case, select it as the current answer).

Efficiency: The algorithm only needs a single pass through the data, making it efficient for streaming data or large datasets where multiple passes are impractical or impossible.

No Extra Space: Aside from variables for counting (
n
) and storing the current answer (ans
), no additional storage is required. This is particularly advantageous when dealing with large data sets where storing all elements in memory would be infeasible.
Here’s a breakdown of how the code works:

Initialization: The constructor simply stores the head of the list for future access.

getRandom Function:
n
is a counter for the nodes seen so far.ans
will store the value of the randomly selected node. The loop iterates over each node in the list one by one.
 For each node, it increments
n
(the count of nodes encountered so far). x
is assigned a random integer between 1 andn
. This random number decides if the current node’s value should replace the previousans
value. If
x
is equal ton
, thenans
is updated to the current node’s value. The probability of this happening is1/n
, ensuring that each node has an equal chance of being chosen. For example, when you’re at the first node,n
is 1, so the probability of choosing that node is 100%. When you’re at the second node, there’s a 50% chance it becomes the answer, and so on.  Finally, after traversing all nodes,
ans
holds the value of a randomly selected node, which is returned.
Why It Works
The key part of this algorithm is the probability calculation that ensures each node has an equal chance of being selected. When you’re at the ith node, the probability that it gets chosen is 1/i
. For it to be the final answer, it must also not be replaced by subsequent nodes. For the ith node and the next node, the probability that the ith node stays as the answer is (1/i) * (1  1/(i+1)) = 1/(i+1)
, and this logic extends to all nodes in the list.
Complexity
 Time Complexity:
O(N)
, whereN
is the number of nodes in the list, since it iterates through each node once.  Space Complexity:
O(1)
, as it uses only a few variables for any size of input linked list.

/** * Definition for singlylinked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { private ListNode head; private Random random = new Random(); public Solution(ListNode head) { this.head = head; } public int getRandom() { int ans = 0, n = 0; for (ListNode node = head; node != null; node = node.next) { ++n; int x = 1 + random.nextInt(n); if (n == x) { ans = node.val; } } return ans; } } /** * Your Solution object will be instantiated and called as such: * Solution obj = new Solution(head); * int param_1 = obj.getRandom(); */

/** * Definition for singlylinked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* head; Solution(ListNode* head) { this>head = head; } int getRandom() { int n = 0, ans = 0; for (ListNode* node = head; node != nullptr; node = node>next) { n += 1; int x = 1 + rand() % n; if (n == x) ans = node>val; } return ans; } }; /** * Your Solution object will be instantiated and called as such: * Solution* obj = new Solution(head); * int param_1 = obj>getRandom(); */

# Definition for singlylinked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def __init__(self, head: Optional[ListNode]): self.head = head def getRandom(self) > int: n = ans = 0 head = self.head while head: n += 1 x = random.randint(1, n) if n == x: ans = head.val head = head.next return ans # Your Solution object will be instantiated and called as such: # obj = Solution(head) # param_1 = obj.getRandom() ############ # Definition for singlylinked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None import random class Solution(object): def __init__(self, head): """ @param head The linked list's head. Note that the head is guaranteed to be not null, so it contains at least one node. :type head: ListNode """ self.head = head def getRandom(self): """ Returns a random node's value. :rtype: int """ ans = self.head.val head = self.head idx = 1 while head: if random.randrange(1, idx + 1) == idx: ans = head.val head = head.next idx += 1 return ans # Your Solution object will be instantiated and called as such: # obj = Solution(head) # param_1 = obj.getRandom()

/** * Definition for singlylinked list. * type ListNode struct { * Val int * Next *ListNode * } */ type Solution struct { head *ListNode } func Constructor(head *ListNode) Solution { return Solution{head} } func (this *Solution) GetRandom() int { n, ans := 0, 0 for node := this.head; node != nil; node = node.Next { n++ x := 1 + rand.Intn(n) if n == x { ans = node.Val } } return ans } /** * Your Solution object will be instantiated and called as such: * obj := Constructor(head); * param_1 := obj.GetRandom(); */