友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
382. 链表随机节点
给你一个单链表，随机选择链表的一个节点，并返回相应的节点值。每个节点 被选中的概率一样 。
实现 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, 10^4^]内 -
-104 <= Node.val <= 104 -
至多调用
getRandom方法104次
进阶：
-
如果链表非常大且长度未知，该怎么处理？
-
你能否在不使用额外空间的情况下解决此问题？
思路分析
总体上两个思路：
-
将 Link List 转换成 Array List
-
计算总数，每次随机生成一个数字，从头向后遍历到该节点数字。
看题解，还发现一个蓄水池抽样算法，但是我感觉不如直接选择一个随机数字，直接向后遍历更高效。
想到一个点：蓄水池抽样算法可以在不知道长度的链表中随机选择节点。
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-07-27 21:16:24
*/
class Solution {
// 方案一：将节点存入 ArrayList 中。
// private Random random;
// private List<ListNode> nodes;
// public Solution(ListNode head) {
// nodes = new ArrayList<>();
// while (head != null) {
// nodes.add(head);
// head = head.next;
// }
// random = new Random();
// }
//
// public int getRandom() {
// if (nodes == null || nodes.size() == 0) {
// return 0;
// }
// return nodes.get(random.nextInt(nodes.size())).val;
// }
// 方案三：将 Link List 转换成 ArrayList
private Random random;
private List<Integer> nodes;
public Solution(ListNode head) {
nodes = new ArrayList<>();
while (head != null) {
nodes.add(head.val);
head = head.next;
}
random = new Random();
}
public int getRandom() {
if (nodes == null || nodes.size() == 0) {
return 0;
}
return nodes.get(random.nextInt(nodes.size()));
}
// 方案二：计算长度，每次都从头向后遍历来取选中的值
// private Random random;
// private int size;
// private ListNode head;
//
// public Solution(ListNode head) {
// random = new Random();
// this.size = 0;
// this.head = head;
// while (head != null) {
// this.size++;
// head = head.next;
// }
// }
//
// public int getRandom() {
// if (size == 0) {
// return 0;
// }
// int num = random.nextInt(size);
// ListNode curr = head;
// for (int i = 0; i < num; i++) {
// curr = curr.next;
// }
// return curr.val;
// }
}