**Solution with detailed explanation** https://leetcode.com/problems/linked-list-random-node/

**Linked List Random Node** https://leetcode.com/problems/linked-list-random-node/

**Algorithm**

- Select first node with p = 1
- Select second node with p = 1/2
- Select kth node with p = 1/k
- Let P(k) be the probability of selecting kth node.
- Probability of kth node being selected after we have seen N elements (N>k) = P(k) * (1-P(k+1)) * (1-P(k+2)) * ... (1 - 1/N) = 1/N

```
from random import randint
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
"""
rnode, count = None, 1
root = self.head
while root:
if randint(1, count) == 1:
rnode = root
root, count = root.next, count + 1
return rnode.val
```