rustgym/leetcode/
_382_linked_list_random_node.rs

1use rand::prelude::*;
2use rustgym_util::*;
3
4struct Solution {
5    head: ListLink,
6    rng: ThreadRng,
7}
8
9impl Solution {
10    fn new(head: ListLink) -> Self {
11        let rng = thread_rng();
12        Solution { head, rng }
13    }
14
15    fn get_random(&mut self) -> i32 {
16        let mut cur = &self.head;
17        let mut res = 0;
18        let mut count = 0;
19        while let Some(node) = cur {
20            let val = node.val;
21            count += 1;
22            if self.rng.gen_range(0, count) == 0 {
23                res = val;
24            }
25            cur = &node.next;
26        }
27        res
28    }
29}