```
import random
class Solution(object):
def __init__(self, head):
self.vals = []
while head:
self.vals += head.val,
head = head.next
def getRandom(self):
return self.vals[random.randint(0, len(self.vals)-1)]
```

This is the version that uses O(1) space but each sampling takes Theta(n) time. 4 lines.

```
import random
class Solution(object):
def __init__(self, head):
self.head = head
def getRandom(self):
cur, res, n = self.head.next, self.head.val, 1
while cur:
res, cur, n = cur.val if random.randint(1, n + 1) == 1 else res,\
cur.next,\
n + 1
return res
```