382. Linked List Random Node

https://leetcode.com/problems/linked-list-random-node/description/

solution

# 直接思路：将链表转化为数组，然后通过数组下标实现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

时间复杂度：O(n) 空间复杂度：O(1)

follow up

随机类小结