Search code examples
algorithmrandomtraversal

Get a random element in single direction linked list by one time traverse

I have a single direction linked list without knowing its size.

I want to get a random element in this list, and I just have one time chance to traverse the list. (I am not allowed to traverse twice or more)

What’s the algorithm for this problem? Thanks!

Solution

  • This is just reservoir sampling with a reservoir of size 1.

    Essentially it is really simple

    1. Pick the first element regardless (for a list of length 1, the first element is always the sample).
    2. For every other element with probability 1/n where n is the number of elements observed so far, you replace the already picked element with the current element you are on.

    This is uniformly sampled, since the probability of picking any element at the end of the day is 1/n (exercise to the reader).