# Clear solution with brief proof of probability

• Let 1/i be the probability of the i-th element as the current element, that is, the probability of this i-th element as the final element will be:

Pr( final element = i )
= ( 1 / i ) { i/(i+1) * (i+1)/ (i+2) * (i+2)/(i+3) * ..... *(n-1)/n }
= ( 1 / i ) * ( i / n )
= 1 / n

• The { } is the probability of all the remaining elements ,which are i+1, i+2, .... , n-1, n, missing as current element.
• Assume there are n elements in the list eventually, but we don't need aware the exact value of n.

Which means each element has same probability as the final element.

``````#Code block
public class Solution {

Note that the head is guaranteed to be not null, so it contains at least one node. */
}

/** Returns a random node's value. */
public int getRandom() {
int cnt = 1;
while (cur != null) {
int ran = (int)(1 + Math.random()*cnt);
if (ran == cnt) { ret = cur.val; }
cnt++;
cur = cur.next;
}

return ret;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.