Random element from a linked list.

Return a random element from list such that each element has equal probability of selection. This needs to be done given that you dont know the size of the linked list. And also in only one scan it should be performed.

Iterate through list from beginning
- Start by choosing between N1 and N2 with a 1/2 chance of picking either one.
- Then pick between ResultOf(N1,N2) and N3 with a 1/3 chance of picking N3 and 2/3 chance of picking ResultOf(N1,N2)
- Then pick between ResultOf(N1,N2,N3) and N4 with a 1/4 chance of picking N4 and 3/4 chance of picking ResultOf(N1,N2,N3)

Solution:
- Keep choosing between previousChoice and NewChoice with a 1/N chance of picking NewChoice and (N-1)/N chance of picking previousChoice where N is the Node number

Proof: If you go thorough the above example, N1 was chosen with a chance of (3/4)(2/3)(1/2)=(1/4)