力扣题目382：链表的随机节点。

---

题目

给定一个单向链表，随即选择链表的一个节点，返回相应的节点数值，每一个节点被选中的概率一样。

要求

实现Solution类：

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

---

思路

链表长度10的4次方，可以初始化的时候遍历整个链表，并且把所有的链表数值预先处理到一个数组之内。
查询的时候随意选择一个数组下标，并且把数组下标对应的内容返回return。

---

代码

class Solution {
    List<Integer> list = new ArrayList<>();
    Random random = new Random(20220116);
    public Solution(ListNode head) {
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }
    }
    public int getRandom() {
        int idx = random.nextInt(list.size());
        return list.get(idx);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

---

结果

Java的Random方法

random方法用于返回一个随机数值，随机数值范围是：0.0 <= Math.random < 1.0。

语法

static double random()
1

参数

• 这是一个默认方法，不带有任何参数。

返回数值

该方法返回的是double数值：

public class Test{
    public static void main(String args[]){
        System.out.println( Math.random() );
        System.out.println( Math.random() );
    }
}
1
2
3
4
5
6