382. Linked List Random Node

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.

 

Example 1:

Input
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1, 2, 3]], [], [], [], [], []]
Output
[null, 1, 3, 2, 2, 3]

Explanation
Solution solution = new Solution([1, 2, 3]);
solution.getRandom(); // return 1
solution.getRandom(); // return 3
solution.getRandom(); // return 2
solution.getRandom(); // return 2
solution.getRandom(); // return 3
// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.

 

Constraints:

  • The number of nodes in the linked list will be in the range [1, 104]
  • -104 <= Node.val <= 104
  • At most 104 calls will be made to getRandom.

 

Follow up:

  • What if the linked list is extremely large and its length is unknown to you?
  • Could you solve this efficiently without using extra space?

Rust Solution

use rand::prelude::*;
use rustgym_util::*;

struct Solution {
    head: ListLink,
    rng: ThreadRng,
}

impl Solution {
    fn new(head: ListLink) -> Self {
        let rng = thread_rng();
        Solution { head, rng }
    }

    fn get_random(&mut self) -> i32 {
        let mut cur = &self.head;
        let mut res = 0;
        let mut count = 0;
        while let Some(node) = cur {
            let val = node.val;
            count += 1;
            if self.rng.gen_range(0, count) == 0 {
                res = val;
            }
            cur = &node.next;
        }
        res
    }
}

Having problems with this solution? Click here to submit an issue on github.