The proof can be proved by induction.

When I first submit my solution, it won't accept for the long test cases, but when I tried it again, it accepted.

Ref: reservoir sampling

```
class Solution(object):
def __init__(self, head):
self.head=head
def getKitem(self,k):
cur=self.head
i,res=0,[0]*k
while cur and i<k:
res[i]=cur.val
cur=cur.next
i+=1
while cur:
# select j from 0-i
j=random.randint(0, i)
# if the pick index less than k, replace it
if j<k:
res[j]=cur.val
cur=cur.next
i+=1
return res
def getRandom(self):
return self.getKitem(1)[0]
```