```
import random
class Solution(object):
def __init__(self, head):
"""
@param head The linked list's head. Note that the head is guanranteed to be not null, so it contains at least one node.
:type head: ListNode
"""
self.head = head
def getRandom(self):
"""
Returns a random node's value.
:rtype: int
"""
reservoir, head, pos = self.head, self.head.next, 1
while head:
index = random.randint(0, pos)
if index == 0:
reservoir = head
head = head.next
pos += 1
return reservoir.val
# Your Solution object will be instantiated and called as such:
# obj = Solution(head)
# param_1 = obj.getRandom()
```

Wish to see NP-complete problems, semaphore problems, and geometry problems as well!

Proof:

1.Probability of first k items still in reservoir finally is that of never getting chosen in the process:

kth item...k+1th item......nth item

k/(k+1) * (k+1)/(k+2) * ... * (n-1)/n = k/n

2.Probability of i'th item in reservoir finally is that of getting chosen at its round and never getting chosen later:

k/i * i/(i + 1) * ... * (n-1)/n = k/n