Return the value of a uniformly random node from a singly linked list, using a solution that works even when the list length is unknown in advance.
Problem
You are given the head of a singly linked list. Design a way to return the value of a node chosen uniformly at random from the list.
Each node should have the same probability of being selected, regardless of the list length. The list is not necessarily stored in an array, and you should assume you may only traverse it through next pointers.
Implement a class that supports:
- initialization with the linked list head
getRandom(): return the value of a randomly chosen node
Goal
Every node in the list must be selected with equal probability.
Input Format
- The linked list head is provided to the constructor.
getRandom()is called repeatedly after construction.
Output Format
getRandom()returns the value stored in one randomly selected node.- Over many calls, each node should be chosen with equal probability.
Constraints
- The list contains at least 1 node.
- Node values may repeat.
- You should aim for a solution that does not require storing all node values in extra space if possible.
Example 1
Input
Linked list: 1 -> 2 -> 3 Calls: getRandom(), getRandom(), getRandom()
Output
One possible output: 2, 1, 3
Explanation
Each call may return any node value, and over many calls each node should be selected with the same probability.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.