Medium

题目描述

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

实现 Solution 类：

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

示例 1：

输入
["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^4] 内
  • -10^4 <= Node.val <= 10^4
  • 至多调用 getRandom 方法 10^4 次

进阶：

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

解题思路

本题提供两种经典解法：

方法一：预处理存储（推荐）

最直观的解法是在构造函数中遍历链表，将所有节点值存储到数组中。这样在 getRandom() 时可以直接生成随机索引返回对应值。时间复杂度为 O(1)，但需要 O(n) 额外空间。

方法二：蓄水池抽样算法

这是一种经典的在线算法，特别适合处理数据流或长度未知的情况。核心思想是：

  • 遍历链表时，第 i 个节点被选中的概率为 1/i
  • 具体实现：遍历到第 i 个节点时，以 1/i 的概率选择当前节点替换之前的结果
  • 数学证明：每个节点最终被选中的概率都是 1/n

蓄水池抽样的优势是空间复杂度为 O(1)，非常适合处理大数据流。虽然每次查询的时间复杂度是 O(n)，但在某些场景下（如内存受限）这是最优选择。

对于 LeetCode 的测试规模，两种方法都可以通过，但方法一在查询频繁时性能更好。

代码实现

class Solution {
private:
    vector<int> nums;
    
public:
    Solution(ListNode* head) {
        while (head) {
            nums.push_back(head->val);
            head = head->next;
        }
    }
    
    int getRandom() {
        int idx = rand() % nums.size();
        return nums[idx];
    }
};

class Solution:

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

    def getRandom(self) -> int:
        import random
        return random.choice(self.nums)

public class Solution {
    private List<int> nums;
    private Random random;

    public Solution(ListNode head) {
        nums = new List<int>();
        random = new Random();
        while (head != null) {
            nums.Add(head.val);
            head = head.next;
        }
    }
    
    public int GetRandom() {
        int idx = random.Next(nums.Count);
        return nums[idx];
    }
}

var Solution = function(head) {
    this.nums = [];
    while (head) {
        this.nums.push(head.val);
        head = head.next;
    }
};

Solution.prototype.getRandom = function() {
    const idx = Math.floor(Math.random() * this.nums.length);
    return this.nums[idx];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

方法时间复杂度空间复杂度
预处理存储初始化 O(n)，查询 O(1)O(n)
蓄水池抽样初始化 O(1)，查询 O(n)O(1)

相关题目