The original article is available at https://dawnmagnet.top/leetcode/2022/01/16/.

Given a singly linked list, randomly select one of its nodes and return the selected node’s value. Every node must have the same probability of being selected.

Implement the Solution class:

• Solution(ListNode head) initializes the object with an integer array.
• int getRandom() randomly selects a node from the linked list and returns its value. Every node in the list must have an equal probability of being selected.

Example:

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(); // returns 1
solution.getRandom(); // returns 3
solution.getRandom(); // returns 2
solution.getRandom(); // returns 2
solution.getRandom(); // returns 3
// The getRandom() method should randomly return one of 1, 2, and 3, with equal probability for each element.

Constraints:

• The number of nodes in the linked list is in the range [1, \(10^4\)].
• \(-10^4\) <= Node.val <= \(10^4\)
• getRandom is called at most \(10^4\) times.

Follow-up:

• How should this be handled if the linked list is very large and its length is unknown?
• Can you solve the problem without using extra space?

Source: LeetCode Link: https://leetcode-cn.com/problems/linked-list-random-node Copyright belongs to LeetCode. For commercial use, contact the official copyright holder; for non-commercial use, cite the source as required.

Analysis

#

Problems like this often look simple and are easy to solve at a basic level, but satisfying every follow-up requirement is much more challenging.

Rather than viewing the input as an ordinary linked list, it is more useful to view it as a data stream of unknown length. The real challenge is to sample a random value from a stream whose length is unknown, as the follow-up makes clear, while also using constant extra space. If the stream is very long but the algorithm needs more than constant space, such as \(O(n)\), the algorithm would be impractical.

This is where the reservoir sampling algorithm is useful. It is completely normal not to know it at first; after seeing it a few times, the idea becomes familiar.

Remember one thing: reservoir sampling is used to obtain a random value from a data stream of unknown length.

Suppose we have processed \(n\) numbers and selected one of the first \(n\) numbers uniformly at random. Each number has probability \(\frac1n\) of being selected. If we add a new number, the \((n+1)\)-th number, we want every number to have probability \(\frac1{n+1}\), including the new number.

How can we make this change in probability? Ensure that the \((n+1)\)-th number is selected with probability \(\frac1{n+1}\). Once that is true, each of the first \(n\) numbers was previously selected with equal probability, so retaining the previous result with probability \(\frac n{n+1}\) makes the probability of each old number \(\frac1{n+1}\) as well.

This is a brief explanation and proof of reservoir sampling. Consult additional references if you would like a more detailed treatment.

The algorithm is now clear. For the \(n\)-th number, generate a random number. If the generated choice selects the current number with probability \(\frac1n\), replace the result with the \(n\)-th number; otherwise leave the result unchanged and continue through the stream.

On the LeetCode platform, Rust supports a third-party random-number library named rand. Its documentation is available at https://docs.rs/rand/latest/rand/.

Rust Code

#

use rand::prelude::*;
struct Solution {
    node: Option<Box<ListNode>>
}
impl Solution {
    fn new(head: Option<Box<ListNode>>) -> Self {
        Solution { node: head }
    }
    fn get_random(&self) -> i32 {
        let mut node = self.node.clone();
        let mut res = 0;
        let mut factor = 1;
        let mut rng = rand::thread_rng();
        while let Some(node_some) = node {
            let rnd: i32 = rng.gen();
            if rnd % factor == 0 {
                res = node_some.val;
            }
            factor += 1;
            node = node_some.next;
        }
        res
    }
}