Description
Given a singly linked list, return a random node's value with equal probability. Use reservoir sampling.
Examples
Input:
head = [1,2,3]Output:
1, 2, or 3 with equal probabilityExplanation:
Random selection from list.
Input:
head = [1]Output:
1, 2, or 3 with equal probabilityExplanation:
Edge case with a single-element array.
Input:
head = [5,10,15,20,25]Output:
5, 10, 15, 20, or 25 with equal probabilityExplanation:
With 5 nodes in the linked list, reservoir sampling ensures each node has a 1/5 (20%) probability of being selected. The algorithm processes each node sequentially, updating the selected node with decreasing probability to maintain uniform distribution.
Constraints
- •
Number of nodes in range [1, 10⁴]