Watch 10 video solutions for Linked List Random Node, a medium level problem involving Linked List, Math, Reservoir Sampling. This walkthrough by NeetCode has 159,494 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 singly-linked list head.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:
[1, 104].-104 <= Node.val <= 104104 calls will be made to getRandom.
Follow up:
Problem Overview: You receive the head of a singly linked list and must implement getRandom() so that every node value has the same probability of being returned. The challenge is that the list length may be unknown, and the structure only allows sequential traversal.
Approach 1: Preprocessing with Array (Time: O(1) per query, Space: O(n))
Traverse the linked list once during initialization and copy every node value into an array. When getRandom() is called, generate a random index between 0 and n-1 and return the value at that position. Array indexing is constant time, so each query is extremely fast. The trade‑off is memory usage: storing all node values requires O(n) extra space.
This approach works well when the list size is moderate and getRandom() is called many times. The one‑time preprocessing cost amortizes nicely across repeated queries.
Approach 2: Reservoir Sampling (Time: O(n) per query, Space: O(1))
When extra memory is restricted or the list length is unknown, use reservoir sampling. Iterate through the list while maintaining a candidate result. For the first node, select it as the current answer. For each subsequent node at position i, replace the stored value with probability 1/i. This probability rule guarantees that every node has equal probability of being chosen after the traversal finishes.
The algorithm works because each element survives the replacement process with equal likelihood. Only one variable stores the current candidate, so space remains constant. This method belongs to the family of randomized algorithms designed for streaming or unknown‑size data.
Recommended for interviews: Reservoir Sampling. Interviewers typically expect this solution because it demonstrates understanding of probability and algorithms for streaming data. The array preprocessing approach shows practical thinking, but the reservoir technique proves you know how to maintain uniform randomness without storing the entire dataset.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Preprocessing with Array | O(n) preprocessing, O(1) per getRandom() | O(n) | When memory is available and getRandom() will be called many times |
| Reservoir Sampling | O(n) per getRandom() | O(1) | When list size is unknown or memory is constrained |