每日一题：382. 链表随机节点（随机算法）

382. 链表随机节点

给你一个单链表，随机选择链表的一个节点，并返回相应的节点值。每个节点 被选中的概率一样 。

实现 Solution 类：

• Solution(ListNode head) 使用整数数组初始化对象。
• int getRandom() 从链表中随机选择一个节点并返回该节点的值。链表中所有节点被选中的概率相等。

示例：

输入
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1, 2, 3]], [], [], [], [], []]
输出
[null, 1, 3, 2, 2, 3]

解释
Solution solution = new Solution([1, 2, 3]);
solution.getRandom(); // 返回 1
solution.getRandom(); // 返回 3
solution.getRandom(); // 返回 2
solution.getRandom(); // 返回 2
solution.getRandom(); // 返回 3
// getRandom() 方法应随机返回 1、2、3中的一个，每个元素被返回的概率相等。

提示：

• 链表中的节点数在范围 [1, 104] 内
• -104 <= Node.val <= 104
• 至多调用 getRandom 方法 104 次

进阶：

• 如果链表非常大且长度未知，该怎么处理？
• 你能否在不使用额外空间的情况下解决此问题？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/linked-list-random-node
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

方法一：链表转化成列表，然后随机索引访问

链表转换成列表，然后进行取随机整数，范围是从0~length-1,或者使用python内置的random.choice函数，该方法时间复杂度o(1)，空间复杂度o(n)，在链表非常大且长度未知时开销较大。

class Solution:
    def __init__(self, head: Optional[ListNode]):
        self.arr = []
        while head:
            self.arr.append(head.val)
            head = head.next

    def getRandom(self) -> int:
        return choice(self.arr)

方法二：水塘抽样/蓄水池抽样

class Solution:
    def __init__(self, head: Optional[ListNode]):
        self.head = head

    def getRandom(self) -> int:
        node, i, ans = self.head, 1, 0
        while node:
            if randrange(i) == 0:  # 1/i 的概率选中（替换为答案）
                ans = node.val
            i += 1
            node = node.next
        return ans

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/linked-list-random-node/solution/lian-biao-sui-ji-jie-dian-by-leetcode-so-x6it/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

其他随机算法

洗牌算法
洗牌算法改进Fisher-Yates