LeetCode 题解工作台
链表随机节点
给你一个单链表，随机选择链表的一个节点，并返回相应的节点值。每个节点 被选中的概率一样 。 实现 Solution 类： Solution(ListNode head) 使用整数数组初始化对象。 int getRandom() 从链表中随机选择一个节点并返回该节点的值。链表中所有节点被选中的概率相等…
4
题型
4
代码语言
3
相关题
当前训练重点
中等 · 链表指针操作
答案摘要
class Solution: def __init__(self, head: Optional[ListNode]):
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 链表指针操作 题型思路
题目描述
给你一个单链表，随机选择链表的一个节点，并返回相应的节点值。每个节点 被选中的概率一样 。
实现 Solution 类：
Solution(ListNode head)使用整数数组初始化对象。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, 104]内 -104 <= Node.val <= 104- 至多调用
getRandom方法104次
进阶：
- 如果链表非常大且长度未知，该怎么处理？
- 你能否在不使用额外空间的情况下解决此问题？
解题思路
方法一
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def __init__(self, head: Optional[ListNode]):
self.head = head
def getRandom(self) -> int:
n = ans = 0
head = self.head
while head:
n += 1
x = random.randint(1, n)
if n == x:
ans = head.val
head = head.next
return ans
# Your Solution object will be instantiated and called as such:
# obj = Solution(head)
# param_1 = obj.getRandom()
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(N) for initial traversal or O(1) per getRandom call with reservoir sampling if counting is done incrementally. Space complexity is O(1) if only pointers and counters are stored, avoiding extra arrays. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Check if you can implement getRandom without storing all node values in an array.
- question_mark
Expect discussion on uniform probability correctness with repeated calls.
- question_mark
Look for use of reservoir sampling or careful pointer updates instead of naïve selection.
常见陷阱
外企场景- error
Replacing selected value incorrectly with wrong probability, causing biased selection.
- error
Assuming linked list length is known without counting, leading to index errors.
- error
Using extra space unnecessarily instead of O(1) pointer-based methods.
进阶变体
外企场景- arrow_right_alt
Return k random nodes from a linked list with uniform probability.
- arrow_right_alt
Support modifications to the linked list between getRandom calls while maintaining uniform selection.
- arrow_right_alt
Implement a weighted random selection where nodes have different probabilities based on their values.