For the follow-up question, if the linked list is very long, we can’t put them into a array-based list and used a random index to get the result-there is not enough space doing that. Then, the only way of solving the problem is to get the result while iterating the linked list.

We must get the random number as we iterate

  1. For list of size 1, we just return that incoming node value;
  2. For list of size 2, we first keep the first one, when the second one comes, we return one of them with P = 1 / 2;
  3. How about size 3? We do the first two step the same as above, when the 3rd element comes, we return it as the result with P = 1 / 3. Remember that the 1st and 2nd element is chosen with P = 1 1 / 2 for the first two iteration, with 3rd one coming with P = 1 / 3 to be chosen as final result, the first two elements now have P = 1 / 2 2 / 3 = 1 / 3 chance to be chosen as the result;
  4. For size of n, we apply the same procedure, choose the nth element with P = 1 / n, thus every other element has P = 1 / (n - 1) * (n - 1) / n = 1 / n;