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

i have single direction linked list without knowing size.

i want random element in list, , have one time chance traverse list. (i not allowed traverse twice or more)

what’s algorithm problem? thanks!

this reservoir sampling reservoir of size 1.

essentially simple

1. pick first element regardless (for list of length 1, first element sample).
2. for every other element probability 1/n n number of elements observed far, replace picked element current element on.

this uniformly sampled, since probability of picking element @ end of day 1/n (exercise reader).