Linked List Random Node
MediumArrayMathLinked ListGraph
Description
Given a singly linked list, return a random node's value with equal probability. Use reservoir sampling and return any value present in the list.
Examples
Input:
head = [1,2,3]Output:
1, 2, or 3Explanation:
Each node value is equally likely, so any of the three node values can be returned across many calls.
Input:
head = [1]Output:
1Explanation:
A single-node list has only one possible value to return.
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⁴]