刷力扣的人应该都有这种体验遇到一道题题目本身读起来很短但真正动手之后才发现背后藏的坑和知识点远比想象中深。Linked List Random Node就是典型代表。它出现在力扣热题里题面只有一句话给定一个单链表等概率返回某个节点的值。可就是这个“等概率”把解法从最朴素的“先数长度再随机”一路推到了“水塘抽样”也让这道看起来只有中等难度的题成了面试官最爱追问的常客。这道题适合谁如果你在准备算法面试或者刚接触链表、随机类题目不久那这篇笔记值得从头看到尾。你不仅能拿到两种解法还能搞明白为什么水塘抽样在这里是正解以及它背后的概率推导是怎么完成的。我会把实际调试中踩过的坑一并写出来最后的常见问题速查表可以直接当复习清单用。1. 题目拆解与核心考点1.1 题面到底在问什么原题要求很简洁你需要设计一个数据结构构造函数接收单链表的头节点getRandom()方法以等概率返回链表中某个节点的值。注意是返回节点的值不是返回节点本身。链表节点结构是 LeetCode 标准的单链表节点public class ListNode { int val; ListNode next; ListNode(int x) { val x; } }第一眼看过去这题比反转链表还简单不就是随机挑一个节点嘛。但仔细一想就会发现一个关键矛盾单链表只能从头往后走不能随机访问。数组可以靠下标一步到位链表做不到。你想随机挑第 k 个节点就必须从头走到第 k 个位置这就逼着你考虑几个问题链表长度是多少如果不知道长度怎么保证“等概率”如果链表特别长甚至长到内存放不下只能从头到尾扫描一次怎么办如果每次getRandom()都从头走一遍时间复杂度能不能接受这三个问题恰好对应了这道题真正的考点等概率的正确性、遍历次数的限制、以及空间复杂度的边界。很多人在力扣上提交通过之后就走了完全没有意识到自己只是“碰巧写对了”并没有真正理解题目要训练的能力。1.2 一道“中等题”背后藏了三个层次我刷这道题时的体会是它其实有三种层次的解法每往上走一层对算法的理解就更深一层。第一层先计数再随机。遍历一遍链表数出总长度 n然后用随机数生成器生成一个[0, n-1]的整数 index再从链表头走 index 步返回那个节点的值。这个解法完全符合直觉代码也好写但它要求链表长度已知且可重复遍历。第二层未知长度一次遍历水塘抽样。这是面试官真正想看的东西。如果链表长度未知或者数据是一个流式输入你只有一次遍历机会每遇到一个节点都要立刻决定保留还是丢弃而且最终每个节点被选中的概率必须都一样。这个场景下水塘抽样的思路几乎是唯一正解。第三层理解和证明为什么水塘抽样能保证等概率。很多人能背出水塘抽样的代码但被问到“为什么第 i 个元素要以 1/i 的概率替换当前结果”时就卡住了。这层不是背代码能解决的需要真正理解概率推导的连乘约分逻辑。后面我会按这三个层次逐步展开。老实说如果你只想 AC 这道题第一层就够了两分钟能写完但如果你想在面试里不被追问倒第二层和第三层是躲不掉的。2. 解法一先求长度再随机取值2.1 思路与完整代码思路很直接第一遍遍历统计链表长度得到 n第二遍遍历走到随机下标对应的位置返回节点值。随机下标用Random.nextInt(n)生成它返回[0, n)的整数刚好覆盖所有节点。Java 实现如下import java.util.Random; class Solution { private ListNode head; private Random random; public Solution(ListNode head) { this.head head; this.random new Random(); } public int getRandom() { // 第一遍统计链表长度 int len 0; ListNode cur head; while (cur ! null) { len; cur cur.next; } // 生成 [0, len-1] 的随机下标 int target random.nextInt(len); // 第二遍走到目标位置 cur head; while (target 0) { cur cur.next; target--; } return cur.val; } }这段代码没什么记忆负担getRandom()的执行流程拆开就是“数一下跳一下”。时间复杂度是 O(n)因为最坏情况下要遍历两遍链表空间复杂度 O(1)除了头指针和一个随机数对象没有额外存储。2.2 复杂度分析与适用边界单次getRandom()的复杂度是 O(n)这里 n 是链表长度。注意这个 O(n) 不能优化到 O(1)——你没法做到真正“随机”的同时又避免遍历因为链表没有索引跳到第 k 个节点本身就需要 k 步。第一次看到有人问那我能不能在构造函数里把链表转成数组这样getRandom()就能 O(1) 了。可以但代价是空间复杂度变成 O(n)。这是完全合法的解法在力扣上也能通过因为题目没有禁止额外空间。如果链表很长内存压力会变大但如果链表本身就不长这个做法反而比两次遍历快得多。什么时候选数组缓存我的判断标准是如果getRandom()调用非常频繁而链表只会初始化一次用数组缓存值得如果链表初始化一次后很少调用随机或者链表本身特别大那就用两次遍历。力扣上的测试用例通常不会把这两者差异放大到超时的程度所以两种都能过。2.3 面试官追问时你最容易露怯的三个点这个解法自己 AC 没问题但面试官只要一追问很多人就沉默了。我整理了自己被问过的三个典型问题第一个问题如果链表长度未知甚至是一个只允许读取一次的流你这个解法还能用吗显然不能因为你必须提前知道 n 才能生成随机下标。流式数据根本不允许你回头再走一遍。第二个问题如果链表的长度特别大比如有十亿个节点你确定两次遍历不会超时吗每次都从头走到尾第一次数长度第二次走随机下标均摊下来还是要扫描整个链表。这个开销在大数据场景下是难以接受的。第三个问题如果不允许用额外空间也不允许两次遍历呢这就把路堵死了。你必须在一遍遍历的过程中边走边决定“当前这个节点是不是最终结果”而且还要保证这个决定是等概率的。到了这一步水塘抽样就该上场了。这也是我把这道题单独拎出来写一篇笔记的原因。它不像那些刷一遍就会的套路题而是能自然引出一种在工程上真正有用的随机采样算法。3. 解法二水塘抽样3.1 水塘抽样的直觉用“替换”代替“提前数个数”水塘抽样这个名字听起来很深奥直觉其实特别简单。想象你在参加一个临时召集的活动主办方说最后会从到场的人里随机抽一个人送奖品但大家是陆续到场的你也不知道最后总共会有多少人。为了保证后到的人也有机会主办方想到了一个规则每到一个新人就以“1 ÷ 当前总人数”的概率把之前选中的那个人换成新人。举个例子第 1 个人来了当前就他一个人所以选中他的概率是 1。第 2 个人来了要以 1/2 的概率替换也就是第 1 个人有 1/2 的概率被保留。第 3 个人来了要以 1/3 的概率替换前两个人各还有 2/3 的概率被保留。到活动结束时每个人留在“候选位”上的概率会相互抵消最后都是 1/n。对应到这道题我拿链表的头节点值作为初始候选然后从第二个节点开始每遇到一个新节点就以“1 / 当前节点序号”的概率替换掉候选值。等链表遍历完候选值就是最终返回的结果。这跟解法一的本质区别是你不需要知道链表有多长也不需要回头遍历第二遍。每一个节点经过时你只做一次随机判断然后继续往下走。3.2 关键概率推导为什么每个节点被选中的概率都是 1/n这是整道题最核心的部分值得把推导过程完整写一遍。假设链表总共有 n 个节点第一个节点记为第 1 个最后一个记为第 n 个。我的做法是先把第 1 个节点放进候选然后从第 2 个节点开始做替换判断。那么第 i 个节点最终被选中需要满足两个条件第 i 个节点到达时它以1/i的概率替换掉原来的候选之后所有节点到达时它都“不被替换”。第 j 个节点到达时替换前一个候选的概率是1/j所以“不被替换”的概率就是1 - 1/j。于是第 i 个节点最终胜出的概率是P(第 i 个节点最终被选中) (1/i) × (1 - 1/(i1)) × (1 - 1/(i2)) × ... × (1 - 1/n)把后面的每一项展开1 - 1/(i1) i/(i1) 1 - 1/(i2) (i1)/(i2) 1 - 1/(i3) (i2)/(i3) ... 1 - 1/n (n-1)/n所以整个连乘是P (1/i) × (i/(i1)) × ((i1)/(i2)) × ... × ((n-1)/n)注意看分子分母疯狂约分前一项的分母和后一项的分子都一样一路消下去最后剩下P (1/i) × (i/n) 1/n也就是说不管你是第 1 个节点还是第 n 个节点最终被选中的概率都精确等于1/n。这个结果跟链表长度无关跟节点位置无关只跟“替换概率等于 1/当前序号”这个规则有关。我用 n 5 的情况做了个表格方便直观感受概率变化节点序号 i被选为候选的概率后续不被替换的连乘最终概率111/2 × 2/3 × 3/4 × 4/51/521/22/3 × 3/4 × 4/51/531/33/4 × 4/51/541/44/51/551/5不需继续1/5看到没有所有约分最后都殊途同归全部指向1/n。这个推导就是水塘抽样的“定海神针”你现场只要能把连乘约分的逻辑讲清楚面试官基本不会再难为你。3.3 完整 Java 实现代码非常短重点在于理解每一行的语义import java.util.Random; class Solution { private ListNode head; private Random random; public Solution(ListNode head) { this.head head; this.random new Random(); } public int getRandom() { // 先把头节点作为初始候选 int result head.val; // 从第二个节点开始遍历 ListNode cur head.next; int i 2; while (cur ! null) { // 以 1/i 的概率替换当前的候选值 if (random.nextInt(i) 0) { result cur.val; } cur cur.next; i; } return result; } }这里用到了一个关键 APIRandom.nextInt(i)返回[0, i-1]的随机整数。所以 0的概率正好是1/i不多不少。为什么开头不设置result 0而是直接用head.val因为第 1 个节点必须被当成初始候选概率为 1。如果你把result初始化为 0然后从第 1 个节点开始也以1/i判断那第一个节点的选中概率就不是 1 了最终概率就不满足前面的推导。3.4 两种等价的循环写法我见过不少题解写的循环是从头节点就开始判断代码长这样public int getRandom() { ListNode cur head; int result head.val; int count 1; while (cur ! null) { if (random.nextInt(count) 0) { result cur.val; } cur cur.next; count; } return result; }这个写法其实也对。因为循环第一次进入时count 1random.nextInt(1)恒为 0所以必然把result重新赋值为head.val等价于“第 1 个节点以 1 的概率进入候选”。只是白白多调用了一次nextInt而且第一次的result实际上被重复设置了。我自己的习惯是用 3.3 的写法头节点先入候选从第二个节点开始遍历逻辑更直观推导也更顺畅。这两种实现只是写法差异概率上完全等价。4. 实战细节与避坑指南4.1 Random 对象的正确用法很多初学者会在getRandom()里每次new Random()这是一个不好的习惯。Random类本身需要时间种子来初始化频繁创建对象既增加开销又可能因为种子的随机性不足导致多次调用出现相关性。正确的做法是在构造函数里创建一次复用同一个实例。如果你在意线程安全可以用ThreadLocalRandom.current().nextInt(i)它的性能比Random更好而且线程安全。不过力扣的测试环境是单线程调用用哪个都行面试时能说清楚区别就是加分项。还要注意nextInt(n)的边界n必须是正数如果传 0 会抛IllegalArgumentException。如果链表只有一个节点head.next是 null循环压根不会进入所以不会出现i 1时调用nextInt(1)的情况。万一链表是空的这种情况题目默认不会出现但工程上最好加一层判断比如返回自定义的默认值或抛出明确异常。4.2 为什么会“看起来随机实际有偏”这道题最隐蔽的坑是代码写对了测试时感觉分布也对但你没有意识到随机数生成器的好坏会影响结果。Java 默认的Random是线性同余生成器它生成的数字在统计上均匀但如果你每次调用都用同一个种子初始化得到的就是一串完全可预测的序列。我把这行代码写在下面你感受一下问题有多隐蔽// 错误示范固定种子结果可预测 Random random new Random(42);固定种子意味着每次程序运行随机序列完全相同。在本地调试时这很友好因为结果可复现但如果你提交到力扣每次调用的结果是固定的那就不叫随机了。好在正常写法new Random()默认使用系统纳秒时间做种子不会出现这个问题。4.3 空间复杂度到底算不算 O(n)解法二的空间复杂度是 O(1)这个没有争议因为只用了两个指针加一个随机数对象。解法一如果选择把链表转成数组空间复杂度就变成 O(n)这个问题面试官一定会问你能不能用 O(n) 的空间换 O(1) 的随机时间如果链表只有几百个节点当然划算如果链表有几百万个节点就要掂量掂量了。我在实际工程里更倾向于水塘抽样解法因为它不需要额外存储也不需要在构造函数里做多余事情未来如果链表数据源从“内存 list”换成“数据库游标”甚至“实时数据流”代码几乎不用改。这是我觉得这道题最大的工程价值。4.4 多次调用 getRandom 的随机性验证方法AC 之后我还做了一件事写了一个简单测试验证水塘抽样在多次调用下的分布是否真的均匀。思路是初始化一个长度为 5 的链表然后调用getRandom()十万次统计每个值出现的频率。一个比较直观的验证是计算每个值出现的百分比。理论期望是 20%实测结果在我的机器上大概是 19.8% 到 20.3% 之间浮动符合预期。这里贴一下我当时测试用的核心逻辑int[] count new int[5]; ListNode head buildList(5); // 自行构造链表 Solution solution new Solution(head); for (int i 0; i 100000; i) { int val solution.getRandom(); count[val - 1]; } for (int c : count) { System.out.printf(%.2f%% , c / 100000.0 * 100); }输出类似20.05% 19.96% 20.12% 19.88% 19.99%这只是粗略验证严格来说应该用卡方检验来判断是否显著偏离均匀分布但对刷题来说看频率已经足够发现问题了。如果你改动了算法导致概率有偏比如把nextInt(i)写成了nextInt(n)这种验证会第一时间暴露问题。5. 变体拓展与实际工程应用5.1 Follow-up如果链表大到无法全部放入内存力扣上的原题默认链表已经存在内存里但面试官会追一个经典 follow-up如果链表是一个外部数据源比如数据库的表记录你只能一次读取一行不知道总共多少行也不允许把所有行都缓存下来你怎么等概率抽取一行这就是水塘抽样的典型应用场景了。因为算法只保留一个候选值空间复杂度是 O(1)遍历过程中不需要回头天然适配数据流。你会发现解法二在那个场景下几乎不需要改动只是把cur cur.next换成“读下一行数据”本质完全一样。如果你需要抽取 k 个样本而不是一个那就是标准水塘抽样维护一个长度为 k 的候选数组前 k 个元素直接放进去从第 k1 个元素开始以k/i的概率替换数组中的任意一个元素。这样最终每个元素被选中的概率都是k/n。这个变体才是面试中真正高频的追问。5.2 加权水塘抽样每条数据概率不同怎么办实际的业务场景还有一个更难的问题每条数据被抽中的概率不一定相等。比如做线上日志采样时高等级错误日志希望被抽到的概率更高普通日志概率低一些。这就需要加权水塘抽样Weighted Reservoir Sampling。一种直观做法是给每条数据分配一个权重 w然后生成一个 [0, 1) 的随机数用Math.pow(random.nextDouble(), 1.0 / w)作为排序键保留排序键最大的记录。这个技巧叫 exponential order statistics实现简单而且面试时讲出来非常加分。知道它能让你在同类题目里脱颖而出但如果你只准备力扣这个拓展了解即可不需要死磕证明。5.3 现实里哪里真的用到了这种随机取样我自己在工作中遇到过几个类似的取样场景模糊处理细节后可以分享给你第一个是线上服务的错误日志采样。服务请求量巨大不可能把所有日志都存下来于是只随机保留一小部分作为样本用于后续的异常分析。水塘抽样的好处是不需要提前知道日志总量流式处理过程中边来边采样内存占用恒定不变。第二个是数据库统计信息估算。数据库在生成执行计划时需要估算某个字段的唯一值数量或分布一种低成本方式就是从表里随机抽一批数据用样本估算整体。实际数据库用的算法比基础水塘抽样复杂很多但最初的思路一脉相承。第三个是 A/B 实验的流量分配。如果某个实验需要从所有活跃用户里抽取 1% 作为实验组你可以在用户请求进入的边界处用一致性哈希或随机数判断本质上也是一种“等概率入组”的抽样问题。这三个场景的共同点是数据量不可预先穷尽必须边遍历边决定去留内存又要保持很小。这就是为什么“随机与取样”这道题能进入经典题单它真的不只是理论。6. 常见问题与调试实录6.1 自检清单三分钟核对你的代码我把刷这道题时容易踩的坑整理成一个速查表提交前可以对照自检症状可能原因排查方向每次返回的都是头节点值循环没有正确进入或random.nextInt(i)的 i 没有递增检查是否从head.next开始循环内是否有i返回结果偏向链表前面的节点nextInt(count)里的 count 不是“当前节点序号”而是固定值确认 count 初始为 2每遍历一个节点 1返回值分布完全固定每次执行都一样用了固定种子创建 Random改为new Random()不要手动指定种子链表为空时抛空指针没有处理 head 为 null 的边界添加空值判断返回默认值或抛明确异常多次调用 getRandom 性能低解法一每次都要遍历两次链表如果调用频繁可换数组缓存否则用水塘抽样保持单次遍历6.2 一次概率失衡的实际排查我记得自己第一次独立写水塘抽样时出现过一次分布明显的偏差头节点被选中的频率远高于其他节点。我把代码反复看了很久才发现问题原因是我的初始候选不是head.val而是某个固定的默认值。当时我写的是int result -1; ListNode cur head; int i 1; while (cur ! null) { if (random.nextInt(i) 0) { result cur.val; } cur cur.next; i; }这段代码的问题是第一个节点必须以概率 1 进入候选。但这里的result初始为 -1第一个节点只以1/1 1的概率被判定进入候选。看起来没问题确实没问题nextInt(1) 0恒成立所以第一个节点一定会被选中。可是问题在于遍历结束后的最后一步如果最后一个节点恰好没有替换候选结果仍然是之前某个节点这符合预期。真正的问题出在另一个地方我为了让代码看起来“从第一个节点开始判断”初始候选设的是result -1然后在循环里第一个节点必然替换。这是等价写法但一旦你用了result -1循环里某个边界写错为random.nextInt(i 1) 0概率就会变成1/(i1)整个推导就不成立了。这个排查看似简单但如果不做频率统计我根本不会发现概率偏差。所以我还是建议你写完这类随机算法后一定要用第 4.4 节的方法跑一下频率验证。它能帮你在提交之前抓住那些肉眼发现不了的概率问题。6.3 用手算穷举把概率验到骨子里如果你还想再进一步确认自己对算法的理解可以手算一个小链表的情况。我当初用 n 3 的链表穷举了一遍遍历过程节点 1必然进入候选当前候选为 A。节点 2有 1/2 概率替换为 B。节点 3有 1/3 概率替换为 C。那么A 最终胜出A 在节点 2 时不被替换1/2在节点 3 时也不被替换2/3相乘得 1/3。B 最终胜出B 在节点 2 时替换成功1/2在节点 3 时不被替换2/3相乘得 1/3。C 最终胜出C 在节点 3 时替换成功1/3之前不需要任何条件概率也是 1/3。三个节点最终都是 1/3完美等概率。这个手算过程虽然简单但比看十遍推导公式都管用它能让“连乘约分”这个抽象操作变得具体可感。面试时如果被追问你能现场手算这个例子比背出公式要有说服力得多。这道题给我的核心启发是随机性不是靠“随便选一个”实现的而是靠精心设计的概率规则在信息不完备的情况下仍然做到统计意义上的公平。水塘抽样这个思想从刷题到工程都能反复派上用场。下一次你遇到“不知道总数只给一次遍历机会还要等概率抽样”的问题直接回想今天这篇笔记里的连乘推导思路就会有依有据。