# 直接思路：将链表转化为数组，然后通过数组下标实现O(1)的随机取
# Reservoir Sampling思路: 当链表长度未知且只能用常数空间，采用蓄水池算法. (很适合链表无法一次性取到全部, 类似stream)
class Solution(object):
def __init__(self, head):
self.head = head
def getRandom(self):
count = 0
res = None
cur = self.head
while cur:
if random.randint(0, count) == 0:
res = cur.val
count += 1
cur = cur.next
return res