Let **1/i** be the probability of the ** i**-th element as the

**, that is, the probability of this**

*current element***-th element as the**

*i***will be:**

*final element*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 ,, missing as current element.*which are i+1, i+2, .... , n-1, n* - Assume there are
elements in the list eventually,*n***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 {
/** @param head The linked list's head.
Note that the head is guaranteed to be not null, so it contains at least one node. */
private ListNode head = null;
public Solution(ListNode head) {
this.head = head;
}
/** Returns a random node's value. */
public int getRandom() {
ListNode cur = head;
int ret = head.val;
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;
}
}
```