LeetCode 382 链表随机节点

摘要

这道题其实挺有意思的，它要求我们从链表中随机选择一个节点，并返回该节点的值。每个节点被选中的概率要相等。听起来简单，但实际做起来还是需要一些技巧的。如果链表长度已知，我们可以先遍历一遍得到长度，然后随机选择一个索引。但如果链表长度未知，或者链表非常大，就需要用到水塘抽样算法了。

这道题的核心在于如何在不知道链表长度的情况下，保证每个节点被选中的概率相等。今天我们就用 Swift 来搞定这道题，顺便聊聊水塘抽样算法在实际开发中的应用场景。

描述

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

实现Solution类：

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

示例：

输入 ["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次

进阶：

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

这道题的核心思路是什么呢？如果链表长度已知，我们可以先遍历一遍得到长度，然后随机选择一个索引，再遍历到对应位置。但如果链表长度未知，或者链表非常大，就需要用到水塘抽样算法（Reservoir Sampling），它可以在只遍历一次链表的情况下，保证每个节点被选中的概率相等。

题解答案

下面是完整的 Swift 解决方案，包含两种方法：基础方法和进阶方法。

基础方法：已知链表长度

如果链表长度已知或可以预先计算，我们可以用这种方法：

// 链表节点定义publicclassListNode{publicvarval:Intpublicvarnext:ListNode?publicinit(_val:Int){self.val=valself.next=nil}}classSolution{privatevarhead:ListNode?privatevarlength:Int=0init(_head:ListNode?){self.head=head// 计算链表长度varcurrent=headwhilecurrent!=nil{length+=1current=current?.next}}funcgetRandom()->Int{// 随机选择一个索引（0 到 length-1）letrandomIndex=Int.random(in:0..<length)// 遍历到对应位置varcurrent=headfor_in0..<randomIndex{current=current?.next}returncurrent!.val}}

进阶方法：水塘抽样算法（推荐）

如果链表长度未知或非常大，使用水塘抽样算法：

classSolution{privatevarhead:ListNode?init(_head:ListNode?){self.head=head}funcgetRandom()->Int{varcurrent=headvarresult=0varcount=0// 遍历链表whilecurrent!=nil{count+=1// 以 1/count 的概率选择当前节点ifInt.random(in:0..<count)==0{result=current!.val}current=current?.next}returnresult}}

题解代码分析

让我们一步步分析这两种解决方案：

基础方法分析

基础方法适用于链表长度已知或可以预先计算的情况：

init(_head:ListNode?){self.head=head// 计算链表长度varcurrent=headwhilecurrent!=nil{length+=1current=current?.next}}

初始化时，我们遍历一遍链表来计算长度。时间复杂度是 O(n)，其中 n 是链表的长度。

funcgetRandom()->Int{letrandomIndex=Int.random(in:0..<length)varcurrent=headfor_in0..<randomIndex{current=current?.next}returncurrent!.val}

getRandom()方法：

1. 随机选择一个索引（0 到 length-1）
2. 从链表头开始遍历到对应位置
3. 返回该节点的值

时间复杂度是 O(n)，因为最坏情况下需要遍历整个链表。空间复杂度是 O(1)，只使用了常数空间。

优点：

• 实现简单，容易理解
• 每个节点被选中的概率确实相等（1/n）

缺点：

• 需要预先知道链表长度
• 每次getRandom()都需要遍历链表，如果链表很长，性能不好
• 如果链表长度未知，无法使用

进阶方法：水塘抽样算法

水塘抽样算法可以在不知道链表长度的情况下，保证每个节点被选中的概率相等：

funcgetRandom()->Int{varcurrent=headvarresult=0varcount=0// 遍历链表whilecurrent!=nil{count+=1// 以 1/count 的概率选择当前节点ifInt.random(in:0..<count)==0{result=current!.val}current=current?.next}returnresult}

算法原理：

水塘抽样算法的核心思想是：当我们遍历到第 i 个节点时，以 1/i 的概率选择它，替换之前选中的节点。

让我们看看为什么这样能保证每个节点被选中的概率相等：

• 第 1 个节点：被选中的概率是 1/1 = 1
• 第 2 个节点：被选中的概率是 1/2，第 1 个节点保持被选中的概率是 1 × (1 - 1/2) = 1/2
• 第 3 个节点：被选中的概率是 1/3，之前节点保持被选中的概率是 1/2 × (1 - 1/3) = 1/3
• 第 i 个节点：被选中的概率是 1/i，之前节点保持被选中的概率是 1/(i-1) × (1 - 1/i) = 1/i

所以，每个节点最终被选中的概率都是 1/n，其中 n 是链表的长度。

优点：

• 不需要预先知道链表长度
• 只需要遍历一次链表
• 空间复杂度是 O(1)，不需要额外空间
• 适用于链表非常大或长度未知的情况

缺点：

• 每次调用getRandom()都需要遍历整个链表
• 如果链表很长，性能可能不如基础方法（如果长度已知）

为什么水塘抽样算法能工作？

让我们用一个例子来说明。假设链表有 3 个节点：[1, 2, 3]。

遍历过程：

1. 遍历到节点 1：

   • count = 1
   • 随机数范围：[0, 1)，即 {0}
   • 如果随机数是 0，选择节点 1
   • 节点 1 被选中的概率：1/1 = 1
   • result = 1

2. 遍历到节点 2：

   • count = 2
   • 随机数范围：[0, 2)，即 {0, 1}
   • 如果随机数是 0，选择节点 2，替换之前的 result
   • 节点 2 被选中的概率：1/2
   • 节点 1 保持被选中的概率：1 × (1 - 1/2) = 1/2
   • result 可能是 1 或 2

3. 遍历到节点 3：

   • count = 3
   • 随机数范围：[0, 3)，即 {0, 1, 2}
   • 如果随机数是 0，选择节点 3，替换之前的 result
   • 节点 3 被选中的概率：1/3
   • 之前节点保持被选中的概率：1/2 × (1 - 1/3) = 1/3
   • result 可能是 1、2 或 3

最终概率：

• 节点 1 被选中的概率：1/3
• 节点 2 被选中的概率：1/3
• 节点 3 被选中的概率：1/3

每个节点被选中的概率都相等！

示例测试及结果

让我们用几个例子来测试一下这个解决方案：

示例 1：基础测试

// 创建链表 [1, 2, 3]letnode1=ListNode(1)letnode2=ListNode(2)letnode3=ListNode(3)node1.next=node2 node2.next=node3letsolution=Solution(node1)// 调用多次 getRandom()foriin1...10{print("第\(i)次 getRandom():\(solution.getRandom())")}

可能的输出：

第 1 次 getRandom(): 2 第 2 次 getRandom(): 3 第 3 次 getRandom(): 1 第 4 次 getRandom(): 2 第 5 次 getRandom(): 3 第 6 次 getRandom(): 1 第 7 次 getRandom(): 3 第 8 次 getRandom(): 1 第 9 次 getRandom(): 2 第 10 次 getRandom(): 2

每次调用都会返回 1、2 或 3 中的一个，每个值被返回的概率应该大致相等。

示例 2：概率验证

letnode1=ListNode(1)letnode2=ListNode(2)letnode3=ListNode(3)node1.next=node2 node2.next=node3letsolution=Solution(node1)// 统计每个值被选中的次数varcount:[Int:Int]=[:]lettotalCalls=10000for_in0..<totalCalls{letvalue=solution.getRandom()count[value,default:0]+=1}print("调用\(totalCalls)次的结果分布:")for(value,times)incount.sorted(by:{$0.key<$1.key}){letpercentage=Double(times)/Double(totalCalls)*100print(" 值\(value):\(times)次 (\(String(format:"%.2f",percentage))%)")}

可能的输出：

调用 10000 次的结果分布: 值 1: 3334 次 (33.34%) 值 2: 3321 次 (33.21%) 值 3: 3345 次 (33.45%)

可以看到，每个值被选中的概率都接近 33.33%，说明算法是正确的。

示例 3：单节点链表

letnode1=ListNode(42)letsolution=Solution(node1)print("单节点链表 getRandom():\(solution.getRandom())")// 总是返回 42

对于单节点链表，getRandom()总是返回该节点的值。

示例 4：长链表测试

// 创建包含 100 个节点的链表varhead:ListNode?=ListNode(1)varcurrent=headforiin2...100{current?.next=ListNode(i)current=current?.next}letsolution=Solution(head!)// 测试多次调用varresults:[Int]=[]for_in0..<100{results.append(solution.getRandom())}print("长链表测试，前20个结果:\(Array(results.prefix(20)))")

这个测试展示了算法在处理长链表时的表现。

时间复杂度

让我们分析一下两种方法的时间复杂度：

基础方法

• 初始化：O(n)，需要遍历链表计算长度
• getRandom()：O(n)，最坏情况下需要遍历整个链表

如果调用getRandom()k 次，总时间复杂度是 O(n + k×n) = O(k×n)。

水塘抽样算法

• 初始化：O(1)，只需要保存头节点
• getRandom()：O(n)，需要遍历整个链表

如果调用getRandom()k 次，总时间复杂度是 O(k×n)。

虽然两种方法的时间复杂度相同，但水塘抽样算法的优势在于：

• 不需要预先知道链表长度
• 初始化时间更短（O(1) vs O(n)）
• 适用于链表长度未知或非常大的情况

空间复杂度

让我们分析一下两种方法的空间复杂度：

基础方法

• 存储头节点：O(1)
• 存储长度：O(1)
• 总空间复杂度：O(1)

水塘抽样算法

• 存储头节点：O(1)
• 遍历时的临时变量：O(1)
• 总空间复杂度：O(1)

两种方法的空间复杂度都是 O(1)，满足进阶要求（不使用额外空间）。

实际应用场景

水塘抽样算法在实际开发中应用非常广泛，特别是在处理大数据流时：

场景一：日志采样

在处理大量日志时，我们可能只需要采样一部分进行分析：

classLogSampler{privatevarlogStream:[String]privatevarsampleSize:Intinit(logStream:[String],sampleSize:Int){self.logStream=logStreamself.sampleSize=sampleSize}funcsample()->[String]{varsamples:[String]=[]for(index,log)inlogStream.enumerated(){ifsamples.count<sampleSize{samples.append(log)}else{// 以 sampleSize/(index+1) 的概率替换letrandomIndex=Int.random(in:0..<(index+1))ifrandomIndex<sampleSize{samples[randomIndex]=log}}}returnsamples}}

场景二：数据流中的随机元素

在处理数据流时，我们可能需要随机选择一个元素：

classStreamRandomSelector{privatevarstream:[Int]privatevarselectedValue:Int?privatevarcount:Int=0init(stream:[Int]){self.stream=stream}funcprocess()->Int?{forvalueinstream{count+=1ifInt.random(in:0..<count)==0{selectedValue=value}}returnselectedValue}}

场景三：在线算法中的随机选择

在一些在线算法中，我们需要在处理数据流的过程中随机选择元素：

classOnlineRandomSelector<T>{privatevarselected:T?privatevarcount:Int=0funcadd(_element:T){count+=1ifInt.random(in:0..<count)==0{selected=element}}funcgetRandom()->T?{returnselected}}

场景四：分布式系统中的负载均衡

在分布式系统中，我们可能需要从多个服务器中随机选择一个：

classServerSelector{privatevarservers:[String]init(servers:[String]){self.servers=servers}funcselectRandom()->String{varselected=servers[0]foriin1..<servers.count{ifInt.random(in:0..<(i+1))==0{selected=servers[i]}}returnselected}}

总结

这道题虽然看起来简单，但实际上涉及了一个非常重要的算法：水塘抽样算法。

关键点总结：

1. 基础方法：适用于链表长度已知的情况，实现简单但需要预先计算长度
2. 水塘抽样算法：适用于链表长度未知或非常大的情况，只需要遍历一次链表
3. 概率保证：水塘抽样算法能保证每个节点被选中的概率相等（1/n）
4. 空间复杂度：两种方法都是 O(1)，满足进阶要求
5. 实际应用：水塘抽样算法在处理大数据流、日志采样等场景中非常有用

选择建议：

• 如果链表长度已知且不会变化，使用基础方法
• 如果链表长度未知或非常大，使用水塘抽样算法
• 如果需要多次调用getRandom()且链表很长，可以考虑缓存长度（基础方法）或优化水塘抽样算法