链表随机节点

难度: Medium

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

实现 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, 10⁴] 内
-10⁴ <= Node.val <= 10⁴
至多调用 getRandom 方法 10⁴ 次

进阶：

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

Submission

运行时间: 184 ms

内存: 17.3 MB

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


class Solution:

    def __init__(self, head: ListNode):
        """
        @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node.
        """
        self.head = head


    def getRandom(self) -> int:
        """
        Returns a random node's value.
        """
        head = self.head
        node = head
        i = 1
        while head:
            if random.randint(0, i-1) == 0:
                node = head
            head = head.next
            i += 1
        return node.val

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

Explain

该题解使用了一种称为「水塘抽样」的随机算法。基本思路是遍历链表，对于第 i 个节点，以 1/i 的概率选择该节点覆盖之前选中的节点。这样能保证选择每个节点的概率都是 1/n，其中 n 是链表的长度。在遍历过程中，用一个变量 node 来维护当前被选中的节点。遍历结束后，node 即为随机选择的节点。

时间复杂度: O(n)

空间复杂度: O(1)

import random

class Solution:

    def __init__(self, head: ListNode):
        """
        @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node.
        """
        self.head = head

    def getRandom(self) -> int:
        """
        Returns a random node's value.
        """
        head = self.head
        node = head  # 维护当前被选中的节点
        i = 1  # 当前节点的编号
        while head:
            # 以 1/i 的概率选择当前节点覆盖之前选中的节点
            if random.randint(0, i-1) == 0:
                node = head
            head = head.next
            i += 1
        return node.val

Explore

水塘抽样算法设计之初就是为了处理流数据或未知大小的数据集中的随机抽样问题。在处理第 i 个元素时，以 1/i 的概率选择这个元素来确保之前的选择可能被覆盖，这样可以保证每个元素最终被选中的机会是公平的。具体来说，当处理第一个元素时，它被选中的概率是 1；到第二个元素时，第一个元素保留的概率是 1/2，第二个元素被选中的概率也是 1/2；以此类推，每个元素在每一步都有相等的概率保留到最后。因此，每个元素最终被选中的概率都是 1/n。

每次调用`getRandom()`时从头遍历整个链表确实在性能上不是最优的。一种可能的优化是，在初始化时遍历链表，并将节点值存储在数组中。这样，`getRandom()`可以直接通过随机索引来访问数组，大大提升效率。然而，这种方法增加了空间复杂度，因为需要额外的存储空间来保存节点值。此外，如果链表经常变动（添加或删除节点），维护这个数组的成本也会增加。

在水塘抽样中，`random.randint(0, i-1) == 0` 这个条件是用来决定是否将当前遍历到的节点作为新的选中节点。这个随机数范围是 `0` 到 `i-1` 因为要保证每个节点被选中的概率是 1/i。当随机数结果为 0（这个事件发生的概率是 1/i）时，当前节点替换原先被选择的节点。这样，每个节点被最终选中为返回结果的概率均为 1/n，确保了选择的公平性。

如果链表结构频繁变动，如节点的添加或删除，`Solution`类需要相应地更新以保持正确的随机选择。如果使用了数组来存储节点值，每次链表变动时都需要更新这个数组。如果直接操作链表，每次调用`getRandom()`方法前都应重新计算链表长度并调整随机选择逻辑。这可能涉及到重新设计`Solution`类，使其能动态地处理链表长度的变化，或者在每次链表更新时重新初始化类实例。