Linked list random node

Linked List Math Reservoir Sampling Randomized

64.7% acceptance

Jan 12, 2026

3211

722

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. Implement the Solution class: Solution(ListNode head) Initializes the object with the head of the singly-linked list head. 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.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

struct Solution {
  values: Vec<i32>,
}

impl Solution {
  fn new(head: Option<Box<ListNode>>) -> Self {
    let mut values = Vec::new();
    let mut current = head;
    
    while let Some(node) = current {
      values.push(node.val);
      current = node.next;
    }
    
    Solution { values }
  }
  
  fn get_random(&self) -> i32 {
    use std::collections::hash_map::RandomState;
    use std::hash::{BuildHasher, Hash, Hasher};
    
    let state = RandomState::new();
    let mut hasher = state.build_hasher();
    self.values.len().hash(&mut hasher);
    let hash = hasher.finish();
    let idx = (hash as usize) % self.values.len();
    self.values[idx]
  }
}