Return a random node's value from a linked list you can only read once

Question

You get the head of a singly linked list. It may be enormous, so you cannot store all values or even count them first, and you may walk it only once from head to tail.

Return the value of a uniformly random node, each node with probability $1/n$ .

Accepted Answer

The list is just a stream of values whose length you do not know, so this is reservoir sampling with reservoir size 1. Walk once. When you reach the node at position i (0-indexed), overwrite your current answer with its value with probability 1/(i+1). Correctness. The node at position i becomes the running choice with probability 1/(i+1), then must dodge every later overwrite. Its final probability is \frac{1}{i+1}\prod{t=i+1}^{n-1}\left(1 - \frac{1}{t+1}\right) = \frac{1}{i+1}\cdot\frac{i+1}{i+2}\cdots\frac{n-1}{n} = \frac{1}{n}, the same for every node. If instead you want a uniform sample …

Return a random node's value from a linked list you can only read once

Your answer

More Coding questions