382. Linked List Random Node Medium

1/**
2 * [382] Linked List Random Node
3 *
4 * Given a singly linked list, return a random node's value from the linked list. Each node must have the same probability of being chosen.
5 * Implement the Solution class:
6 * 
7 * 	Solution(ListNode head) Initializes the object with the head of the singly-linked list head.
8 * 	int getRandom() Chooses a node randomly from the list and returns its value. All the nodes of the list should be equally likely to be chosen.
9 * 
10 *  
11 * Example 1:
12 * <img alt="" src="https://assets.leetcode.com/uploads/2021/03/16/getrand-linked-list.jpg" style="width: 302px; height: 62px;" />
13 * Input
14 * ["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
15 * [[[1, 2, 3]], [], [], [], [], []]
16 * Output
17 * [null, 1, 3, 2, 2, 3]
18 * Explanation
19 * Solution solution = new Solution([1, 2, 3]);
20 * solution.getRandom(); // return 1
21 * solution.getRandom(); // return 3
22 * solution.getRandom(); // return 2
23 * solution.getRandom(); // return 2
24 * solution.getRandom(); // return 3
25 * // getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.
26 * 
27 *  
28 * Constraints:
29 * 
30 * 	The number of nodes in the linked list will be in the range [1, 10^4].
31 * 	-10^4 <= Node.val <= 10^4
32 * 	At most 10^4 calls will be made to getRandom.
33 * 
34 *  
35 * Follow up:
36 * 
37 * 	What if the linked list is extremely large and its length is unknown to you?
38 * 	Could you solve this efficiently without using extra space?
39 * 
40 */
41pub struct Solution {}
42use crate::util::linked_list::{ListNode, to_list};
43
44// problem: https://leetcode.com/problems/linked-list-random-node/
45// discuss: https://leetcode.com/problems/linked-list-random-node/discuss/?currentPage=1&orderBy=most_votes&query=
46
47// submission codes start here
48
49// Definition for singly-linked list.
50// #[derive(PartialEq, Eq, Clone, Debug)]
51// pub struct ListNode {
52//   pub val: i32,
53//   pub next: Option<Box<ListNode>>
54// }
55// 
56// impl ListNode {
57//   #[inline]
58//   fn new(val: i32) -> Self {
59//     ListNode {
60//       next: None,
61//       val
62//     }
63//   }
64// }
65struct Solution {
66        false
67    }
68
69
70/** 
71 * `&self` means the method takes an immutable reference.
72 * If you need a mutable reference, change it to `&mut self` instead.
73 */
74impl Solution {
75
76    fn new(head: Option<Box<ListNode>>) -> Self {
77        
78    }
79    
80    fn get_random(&self) -> i32 {
81        
82    }
83}
84
85/**
86 * Your Solution object will be instantiated and called as such:
87 * let obj = Solution::new(head);
88 * let ret_1: i32 = obj.get_random();
89 */
90
91// submission codes end
92
93#[cfg(test)]
94mod tests {
95    use super::*;
96
97    #[test]
98    fn test_382() {
99    }
100}
101