algorithm - How would you pick a uniform random element in linked list with unknown length?

Question

How would you pick a uniform random element in linked list with unknown length in one pass or if not two passes?

Answer 1

Use reservoir sampling http://en.wikipedia.org/wiki/Reservoir_sampling . You need only one pass of the data.

For picking one element:

1. Pick first element (probability 1)
2. Later, for kth element pick it with probability 1/k (i.e. replace the existing selection with kth element)

I will let you prove that this results in uniform selection of elements.