企业官网建设流程全解析

LeetCode 382 要求从单向链表中等概率地随机返回一个节点的值。如果链表长度固定，可以遍历一次，把所有值存进数组，然后随机取下标。但题目要求应对“链表十分大且长度未知”的场景，此时蓄水池抽样算法就派上用场了，它能在 O(1) 空间内解决这个问题。

解法一：存储所有节点值（适合长度已知或允许额外空间）

先把链表的所有值存入一个列表，getRandom 时用 Random 生成一个下标并返回对应值。

classSolution{List<Integer>list=newArrayList<>();Randomrandom=newRandom();publicSolution(ListNodehead){while(head!=null){list.add(head.val);head=head.next;}}publicintgetRandom(){returnlist.get(random.nextInt(list.size()));}}

这个写法简单直观，但空间复杂度是 O(n)，不符合题目进阶要求的常数级空间。

解法二：蓄水池抽样（空间 O(1)，推荐）

核心思想是：遍历链表，对第 i 个节点（从 1 开始计数），以 1/i 的概率决定是否用它替换当前保留的结果。遍历结束后，每个节点被选中的概率都是 1/n。

正确性证明（简述）：对于第 i 个节点，它最终被选中的概率 =（在第 i 步被选中的概率 1/i）×（之后每一步都不被替换的概率 i/(i+1) × (i+1)/(i+2) × … × (n-1)/n）= 1/n。因此每个节点的选中概率相等。

Java 实现：

classSolution{privateListNodehead;privateRandomrandom;publicSolution(ListNodehead){this.head=head;this.random=newRandom();}publicintgetRandom(){intres=0;ListNodenode=head;intcount=0;while(node!=null){count++;// 当前是第 count 个节点// 以 1/count 的概率替换结果if(random.nextInt(count)==0){// nextInt(count) 生成 [0, count-1] 的整数，取到 0 的概率是 1/countres=node.val;}node=node.next;}returnres;}}

也可以写成 if ((int)(Math.random() * count) == 0) 的形式，两者等价。

复杂度：

· Solution 构造：O(1)，只保存头节点引用。
· getRandom：O(n) 时间，O(1) 额外空间。
· 如果链表极长且 getRandom 调用频繁，这是时间换空间的经典权衡。

两种方法都能通过题目，但蓄水池抽样是本题的考察重点，也是应对“未知长度、巨大数据量”场景的标准答案。