摘要

这道题挺有意思的：给定一个单链表，每次调用方法时要随机返回链表里的某个节点，而且要求每个节点被选中的概率一样。

听起来就像是“从一群人里随机抽一个人”，但问题是链表不像数组那样能直接通过下标访问，这就让事情变得稍微复杂了一点。我们需要思考怎么在 O(1) 空间 或者 合适的时间复杂度 下解决问题。

这篇文章会带你一步步分析解法，并提供 Swift 的可运行 Demo，还会结合一些实际的应用场景，比如抽签、随机抽样等，让你对题目有更直观的理解。

描述

题目要求我们实现一个类 Solution，它要支持两个操作：

1. 初始化：传入一个链表 head，保存下来。
2. getRandom()：随机返回链表中的某个节点的值，并且要求所有节点的返回概率是相等的。

示例：

输入: [1,2,3]
操作: getRandom() -> 可能返回 1 或 2 或 3

因为是随机，所以多次运行可能会返回不同的结果，但长远来看，每个节点出现的概率要相等。

题解答案

这道题有两种常见的解法：

1. 简单粗暴法：
   先遍历链表，把所有值存到数组里。之后每次调用 getRandom() 时，直接在数组里随机选一个值返回。

   • 优点：实现简单
   • 缺点：需要额外的空间，O(n)

2. 蓄水池抽样（Reservoir Sampling）：
   这是更“进阶”的方法，尤其在链表很长甚至长度未知的情况下特别好用。它的核心思想是：

   • 遍历链表，每次遇到一个新的节点，就以某种概率决定是否选中它。
   • 遍历到最后，保证每个节点被选中的概率都是 1/n。
   • 空间复杂度是 O(1)，非常优雅。

这道题我们先实现 数组法（更直观），再提一下 蓄水池抽样，让大家对进阶解法也有个概念。

题解代码分析

我们先来实现 数组法：

import Foundation

// 链表节点定义
public class ListNode {
    public var val: Int
    public var next: ListNode?
    public init(_ val: Int) {
        self.val = val
        self.next = nil
    }
}

class Solution {
    private var values: [Int]
    
    init(_ head: ListNode?) {
        values = []
        var current = head
        while let node = current {
            values.append(node.val)
            current = node.next
        }
    }
    
    func getRandom() -> Int {
        return values.randomElement()!
    }
}

代码拆解

1. ListNode 定义
   Swift 的链表节点就是一个类，包含 val 和 next 指针。

2. init

   • 初始化时遍历整个链表
   • 把所有节点值存到 values 数组里
   • 这样后续每次随机都能直接操作数组

3. getRandom

   • 调用 randomElement() 从数组中随机挑选一个值
   • 保证所有元素概率相等

这个版本足够应付大多数情况，写起来也非常直观。

示例测试及结果

我们来写个简单的 Demo：

// 构造链表 [1, 2, 3]
let head = ListNode(1)
head.next = ListNode(2)
head.next?.next = ListNode(3)

// 初始化 Solution
let solution = Solution(head)

// 连续调用 getRandom
for _ in 0..<5 {
    print(solution.getRandom())
}

可能输出结果：

2
1
3
2
3

可以看到，每次运行的结果不同，但从长远来看，三个数出现的概率是均等的。

时间复杂度

• 初始化：O(n)，需要遍历一遍链表。
• 每次 getRandom：O(1)，直接数组取值。

空间复杂度

• 额外用了一个数组存储所有节点值，空间复杂度 O(n)。

总结

这道题的本质是“如何在链表这种数据结构上做随机访问”。

• 如果链表不大，最简单的就是转成数组来处理，代码简单好写。
• 如果链表非常大、甚至长度未知，那么更好的方法是 蓄水池抽样，它能在 O(1) 空间内完成随机抽样。

在实际应用中，这种思路很常见，比如：

• 数据流随机采样（比如日志流中随机抽样一部分）
• 随机抽签、抽奖功能
• 在资源有限的情况下，从大量数据中公平地抽取样本

所以这题虽然看起来是个小练习，但背后其实有很强的工程意义。