LeetCode 382. 链表随机节点

Categories:

题目描述
思路分析
1. 解法一：水塘抽样（推荐）
相似题目

题目描述

✅ 382. 链表随机节点

思路分析

解法一：水塘抽样（推荐）

核心思路：

依次遍历链表，第 i 个节点以 1/i 概率替换答案。

保证每个节点被选中的概率相等。

只需一次遍历即可完成随机采样。

复杂度分析：

时间复杂度：O(n)，其中 n 表示链表长度。

空间复杂度：O(1)，仅使用常数额外空间。

class Solution {
    private final ListNode head;
    private final Random random = new Random();

    public Solution(ListNode head) {
        this.head = head;
    }

    public int getRandom() {
        int ans = 0;
        int i = 1;
        ListNode cur = head;

        // 水塘抽样
        while (cur != null) {
            if (random.nextInt(i) == 0) {
                ans = cur.val;
            }
            i++;
            cur = cur.next;
        }

        return ans;
    }
}

type Solution struct {
	head *ListNode
}

func Constructor(head *ListNode) Solution {
	return Solution{head: head}
}

func (s *Solution) GetRandom() int {
	ans := 0
	i := 1
	cur := s.head

	// 水塘抽样
	for cur != nil {
		if rand.Intn(i) == 0 {
			ans = cur.Val
		}
		i++
		cur = cur.Next
	}

	return ans
}

相似题目

题目	难度	考察点
398. 随机数索引	中等	水塘抽样
384. 打乱数组	中等	洗牌
382. 链表随机节点	中等	水塘抽样
470. 用 Rand7 实现 Rand10	中等	随机
528. 按权重随机选择	中等	前缀和

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/49521905