382. Linked List Random Node

382

MediumRandomization, Math and Miscellaneous (FAANG add-on)Streaming uniform random selectionReservoir sampling (size 1)

Linked List Random Node

Given the head of a singly linked list, design a data structure that returns the value of a random node, where each node is equally likely to be chosen. Support this even without knowing the list length in advance (follow-up: constant extra space).

Open official problem prompt ↗

In plain English

Return a uniformly random node value from a linked list using only constant extra memory, even if the length is unknown.

Picture it like this

A talent scout interviewing candidates one at a time who can only remember one favorite; each new candidate has a fair chance of becoming the new favorite so that everyone ends up equally likely.

Example

Input: init([1,2,3]); getRandom()
Output: 2
Why: getRandom returns any of 1, 2, or 3 each with probability 1/3; 2 is one valid uniformly-random result.

Constraints

The number of nodes in the list is between 1 and 10^4-10^4 <= Node.val <= 10^4At most 10^4 calls will be made to getRandom

Pattern lesson

See the pattern, then code

Reservoir sampling (size 1)

↗

Randomization, Math and Miscellaneous (FAANG add-on)

Uniform random selection, sampling streams, number theory, or precision-heavy parsing.. Walk the list keeping one candidate; at the i-th node replace the candidate with probability 1/i, which leaves every node with final probability exactly 1/n.

New words, made simpleKnow these before the algorithm

Reservoir sampling: A technique to sample k items uniformly from a stream of unknown length using O(k) memory.
Replacement probability: At the i-th item the current pick is replaced with probability 1/i.
Uniform sampling: Every element has identical selection probability 1/n.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Count then index

Works but requires knowing/traversing length twice and is awkward for true streams.

First pass to get length n, second pass to reach a random index.

Time O(n)Space O(1)

Best choiceReservoir sampling

One pass, constant memory, handles unknown length.

Single pass replacing the held value with probability 1/i.

Time O(n)Space O(1)

The rule we keep true

Invariant

After examining the first i nodes, the value currently held is uniformly random among those i nodes, each with probability 1/i.

Why this is correct

Reasoning

By induction, node i is kept with probability 1/i, and each earlier node keeps its 1/(i-1) probability times the (i-1)/i chance of not being replaced, which equals 1/i; extending to n gives every node probability 1/n.

The algorithm in three movesSay these aloud before coding

1Store the head reference in the constructor

i=1 val=1 chosen (prob 1)

2Scan from the head, tracking a 1-based counter i

i=2 replace with 2 with prob 1/2

3At each node pick a random integer in [1, i]; if it equals 1, adopt this node's value

i=3 replace with 3 with prob 1/3 -> each 1/3

4Return the surviving value after the scan

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readi=1

2 · AskKeep?

3 · Update staterandint(1,1)==1 always

4 · Resultresult=1 with probability 1.

Key takeaway

Reservoir of size one scanning the list; node 2 currently held.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 10-11Constructor
Just store the head; no length precomputation needed.
2
Lines 13-16Scan setup
result holds the current pick, i is the 1-based position.
3
Lines 17-20Reservoir step
With probability 1/i adopt the current node's value, then advance.
4
Lines 21Return
The surviving value is uniformly random across all nodes.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Single-node list always returns that node
Very long lists (10^4 nodes) still use O(1) memory
Negative node values are handled since only values are copied
Many repeated getRandom calls each independently uniform

Common beginner mistakes

Using randint(0, i-1)==0 vs randint(1, i)==1 inconsistently (both work but must be coherent)
Precomputing length in the constructor, which breaks the streaming/follow-up intent
Reusing a stale counter across calls instead of restarting i at 1
Returning the head value always by forgetting to replace

Check your understanding

Why does replacing with probability 1/i yield a uniform distribution?

PyPython 3 · solution.py

Optimal

1import random2from typing import Optional34# Definition for singly-linked list.5# class ListNode:6#     def __init__(self, val=0, next=None):7#         self.val = val8#         self.next = next910class Solution:11    def __init__(self, head: Optional['ListNode']):12        self.head = head1314    def getRandom(self) -> int:15        result = 016        node = self.head17        i = 118        while node:19            if random.randint(1, i) == 1:20                result = node.val21            node = node.next22            i += 123        return result

Time complexityO(n) per getRandom, O(1) constructorOptimized

Space complexityO(1) extraExplained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

GoogleMetaAmazon

Linked List Random Node

Linked List Random Node

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Randomization, Math and Miscellaneous (FAANG add-on)