LeetCode 382. 链表随机节点
目录
题目描述
题意分析
需要设计一个类：构造时拿到一个单链表的头指针，之后每次调用
getRandom都要等概率地返回链表中某个节点的值。等概率的含义是，若链表有 $n$ 个节点，每个节点被返回的概率都恰好是 $1/n$。关键的约束信号有两条。第一，链表不支持下标随机访问，想拿到第 $k$ 个节点必须从头走 $k$ 步。第二，题目进阶部分明确提出「链表十分大且长度未知」，并要求不额外使用空间——这等于禁止了「先遍历一遍存进数组再随机下标」的直白做法，也禁止了「先数一遍长度再走一遍」的两趟做法。
于是真正的难点变成：在只允许单向走一趟、且事先不知道总数的前提下，如何保证每个元素被选中的概率完全一致。
边界情况：链表至少有一个节点，所以不必处理空链表；
getRandom会被调用很多次，每次都是独立的一次抽样，不能让前一次的结果影响后一次。
解法：水塘抽样
核心思路
把链表转成数组后随机取下标很直观，但需要 $O(n)$ 额外空间；先统计长度再定位随机下标虽然只用 $O(1)$ 空间，却需要两趟遍历。题目的「长度未知、只能单趟读取」正是水塘抽样的使用信号。
对于只选一个元素的水塘，先把第一个节点放入水塘。之后遇到第 $i$ 个节点时，以 $1/i$ 的概率用它替换当前答案。关键不变量是：处理完前 $i$ 个节点后，这 $i$ 个节点各以 $1/i$ 的概率留在水塘中。
等概率证明：$i=1$ 时第一个节点必选，不变量成立。假设处理完 $i-1$ 个节点时，每个旧节点的留存概率是 $1/(i-1)$。第 $i$ 个节点以 $1/i$ 的概率被选中；任意旧节点需要先留存、再避免被替换，所以更新后的概率为
\[\frac{1}{i-1}\left(1-\frac{1}{i}\right)=\frac{1}{i-1}\cdot\frac{i-1}{i}=\frac{1}{i}.\]新旧节点的概率都是 $1/i$，归纳成立。遍历结束时 $i=n$，每个节点就都以 $1/n$ 的概率被返回，整个过程无需提前知道 $n$。
解题步骤
- 构造函数只保存头指针，不统计长度，也不复制节点。
- 每次
getRandom都重新开始抽样：先选中头节点，令answer = head.val、seen = 1。- 从第二个节点开始遍历。每读到一个新节点，先把
seen加一，使它表示已处理节点数 $i$。- 在 $[0,i)$ 中均匀生成一个整数；只有结果为 0 时才用当前值替换
answer，因而替换概率恰好是 $1/i$。- 遍历结束后返回
answer。每次调用都应重置answer和seen，但不要重新播种随机数生成器。例如链表
1 -> 2 -> 3：处理节点 2 后，1 和 2 各以 $1/2$ 的概率留存；处理节点 3 时，3 以 $1/3$ 的概率入选，1 和 2 则各以 $\frac{1}{2}\times\frac{2}{3}=\frac{1}{3}$ 的概率留存。
代码实现
import java.util.concurrent.ThreadLocalRandom;
class Solution {
private final ListNode head;
public Solution(ListNode head) {
this.head = head;
}
public int getRandom() {
int answer = head.val;
int seen = 1;
for (ListNode node = head.next; node != null; node = node.next) {
seen++;
if (ThreadLocalRandom.current().nextInt(seen) == 0) {
answer = node.val;
}
}
return answer;
}
}
import "math/rand"
type Solution struct {
head *ListNode
}
func Constructor(head *ListNode) Solution {
return Solution{head: head}
}
func (s *Solution) GetRandom() int {
answer, seen := s.head.Val, 1
for node := s.head.Next; node != nil; node = node.Next {
seen++
if rand.Intn(seen) == 0 {
answer = node.Val
}
}
return answer
}
复杂度分析
- 时间复杂度：构造函数为 $O(1)$；每次
getRandom为 $O(n)$，需要完整遍历链表。- 空间复杂度：$O(1)$。抽样过程只保存指针、计数器和一个候选值。
关键点总结
- 长度未知、只能遍历一次的数据流要等概率选一个元素，用大小为 1 的水塘抽样。
- 第 $i$ 个元素的替换概率是 $1/i$，而不是固定概率或 $1/n$；算法在过程中根本不知道 $n$。
- 正确性证明必须同时覆盖新节点和旧节点：新节点直接以 $1/i$ 入选，旧节点以 $1/(i-1)$ 留存到上一轮后，还要再乘不被替换的概率 $(i-1)/i$。
- 每次
getRandom都要重置抽样状态；随机数生成器则应复用，不要在高频调用中反复播种。- 如果面试官追问一次随机选 $k$ 个，就把水塘扩大到 $k$：前 $k$ 个元素直接入池，第 $i$ 个元素以 $k/i$ 的概率替换池中的随机一个。
易错点总结
- 概率分母写错一位：处理第 $i$ 个节点时必须从 $i$ 个整数中选一个。若写成
nextInt(i + 1) == 0，新节点概率会变成 $1/(i+1)$，分布立即失真。- 计数从 0 开始却直接调用
nextInt(seen)：第一个节点会调用nextInt(0)，Java 抛异常，Go 也会 panic。显式选中头节点可以避免这个偏移错误。- 遍历未结束就返回：水塘中的候选值只对「已读取的前缀」均匀，必须读完所有节点才对整条链表均匀。
- 把抽样候选和计数器存成跨调用状态：第二次
getRandom不再从第一个节点、概率 $1/1$ 开始，将破坏每次抽样的边缘分布。- 每次调用都用低精度时间戳重新播种：短时间连续调用会获得相同随机序列。应使用语言提供的长期随机源，不要在
getRandom内手动播种。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 398. 随机数索引 | 中等 | 在等值下标集合内做水塘抽样 |
| 384. 打乱数组 | 中等 | 洗牌算法，要求整体排列等概率 |
| 528. 按权重随机选择 | 中等 | 前缀和加二分实现非均匀抽样 |
| 497. 非重叠矩形中的随机点 | 中等 | 先按面积加权选矩形，再在矩形内均匀取点 |