leetcode-382

最简单的方式：先用List存储，然后用Random包随机。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:

  def __init__(self, head: Optional[ListNode]):
    self.arr = []
    while head is not None:
      self.arr.append(head.val)
      head = head.next
    self.length = len(self.arr)

  def getRandom(self) -> int:
    import random
    x = random.randint(0, self.length -1)
    return self.arr[x]

# Your Solution object will be instantiated and called as such:
# obj = Solution(head)
# param_1 = obj.getRandom()

满足进阶要求需要使用“蓄水池抽样算法”，第一次听说这个算法，先mark一下，有空了解了写篇博客记下笔记。