Difficulty: MediumLinked List

Linked List Random Node

Problem in Plain English

Choose a uniformly random node from a singly linked list using Reservoir Sampling. Keep one candidate and scan the list without storing all nodes.

Problem Statement

Implement Solution(head) and getRandom(). Each call returns a node value, and every node must have equal selection probability. Duplicate values remain distinct node outcomes. The official exercise provides a nonempty list and asks how to handle unknown length without extra storage. Each snippet expects the judge’s ListNode with fields val and next. The list remains unchanged during sampling. Random transcripts are possible outcomes, not fixed required outputs.

Constraints

1 <= node count <= 10^4.
-10^4 <= Node.val <= 10^4.
At most 10^4 calls to getRandom.
Each call assumes independent uniform draws; sampling treats node identities, not unique values.

Examples

Example 1

Input: Solution([1,2,3]); getRandom()
Output: 1 (one possible result)

With controlled integer draws 1,2,2 from ranges [1,1],[1,2],[1,3], only node 1 replaces the candidate. Values 1,2,3 each have probability 1/3.

Example 2

Input: Solution([-4]); getRandom()
Output: -4

The sole node replaces the candidate with probability one, so every call returns -4.

Example 3

Input: Solution([7,7,9]); getRandom()
Output: 7 with probability 2/3; 9 with probability 1/3

Each node is selected with probability 1/3. The two distinct nodes with value 7 contribute separate equal shares to that value’s probability.

Example 4

Input: Solution([1,2,3]); getRandom() five times
Output: [1,3,2,2,3] (possible transcript)

This is the official example’s possible sequence, excluding the null constructor result. All calls scan anew and each may return any of the three values.

Intuition

Maintain a reservoir of one node. On visiting node i, replace the current candidate with probability 1/i. Early nodes have more chances to be evicted, balancing their earlier selection. For Example 1, choose node 1 automatically, keep it at node 2 with probability 1/2, and keep it at node 3 with probability 2/3: node 1 survives with probability 1/3. Nodes 2 and 3 also finish with probability 1/3. Store the head and restart the scan on every call, so repeated samples do not require a value array.

Approaches

Reservoir Sampling

Optimal

Solution Details

Reveal Reservoir Sampling: intuition, complexity, and code

Intuition

Visit each node once and draw a uniform integer from 1 through the number seen. Replace the candidate exactly when the draw is 1. Java uses Random.nextInt(seen)==0, Python uses randrange(seen)==0, and JavaScript uses floor(random()*seen)==0. The first node always wins its only draw; subsequent draws may replace it. A stored-value baseline makes calls cheap but uses linear memory; this approach is selected for the follow-up’s constant-memory requirement and pays one traversal per call. JavaScript Math.random supplies pseudorandom floating draws; the uniformity proof assumes ideal independent uniform draws, as with all randomized algorithm analyses.

Step-by-Step Logic

Start at head 1 with seen=0 and no visited candidate.
Visit node 1: seen=1, controlled draw 1; select value 1.
Visit node 2: seen=2, controlled draw 2; retain value 1.
Visit node 3: seen=3, controlled draw 2; retain value 1.
Reach null and return 1, one possible result. Restart at the head on the next call.

Why It Works

Induct on the number i of visited nodes. At i=1 the sole candidate has probability one. At step i, the new node is selected with probability 1/i. Every previous node had probability 1/(i-1) and survives with probability (i-1)/i, so its new probability is 1/i. Thus all i nodes are equally likely after each step, in particular after n steps. Equivalently node j is selected at j with probability 1/j and survives later steps with product j/(j+1) × (j+1)/(j+2) × ... × (n-1)/n = j/n, yielding 1/n. Draws must be independent across visits and calls; observed sample frequencies support an implementation check but are not the proof.

Dry Run

Reservoir Sampling: variable states at each step
Visited value	seen	Draw in [1,seen]	Replace?	Candidate
1	1	1	yes	1
2	2	2	no	1
3	3	2	no	1
End of list	3	none	no	1 (one possible result)

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(1)

Construction stores only the head and random generator in constant work. Each getRandom call traverses n nodes with one draw per node and constant auxiliary state; there is no recursion or value array. Up to 10,000 calls on a 10,000-node list means 100 million visits, a real trade-off for constant memory.

Code

Solution.java

1import java.util.Random;2class Solution {3    private final ListNode head;4    private final Random random = new Random();5    public Solution(ListNode head) { this.head = head; }6    public int getRandom() {7        int seen = 0, answer = 0;8        for (ListNode node = head; node != null; node = node.next) {9            seen++;10            if (random.nextInt(seen) == 0) answer = node.val;11        }12        return answer;13    }14}

Hints

Hint 1

Keep one candidate instead of a list of values.

Hint 2

When you have seen i nodes, the new node should win with probability 1/i.

Hint 3

Show that an old node’s probability becomes (1/(i-1))×((i-1)/i)=1/i.

Edge Cases

The first node must always be selected, including a singleton with value zero or a negative value.
Repeated values are separate nodes, so value probabilities need not be equal.
Repeated getRandom calls must reset seen and traverse from the original head.

Common Mistakes and Interview Tips

Replacing with probability 1/2 at every node strongly favors the last nodes.
Keeping seen between calls breaks the per-call uniformity invariant.
Deduplicating values changes the problem from uniform nodes to uniform distinct values.
A few plausible random outputs do not establish correctness; verify controlled transitions and the probability invariant.

Key Takeaway

Reservoir Sampling maintains a uniform sample as an unknown-length stream grows. Its correctness comes from selection and survival probabilities, and its constant memory trades away constant-time resampling.