Linked List Random Node

medium linked list reservoir sampling

Problem

Return a uniformly random node value from a linked list of unknown length using O(1) extra memory.

Inputhead = 1 → 2 → 3 → 4 → 5

Outputany of {1, 2, 3, 4, 5} with prob 1/5

Walk once; at node i (1-indexed), replace the answer with this value with probability 1/i.

list values

RNG seed

import random

class Solution:
    def __init__(self, head):
        self.head = head
    def getRandom(self):
        ans, i = self.head.val, 1
        node = self.head.next
        while node:
            i += 1
            if random.randint(1, i) == 1:
                ans = node.val
            node = node.next
        return ans

class Solution {
  constructor(head) { this.head = head; }
  getRandom() {
    let ans = this.head.val, i = 1;
    for (let node = this.head.next; node; node = node.next) {
      i++;
      if (Math.floor(Math.random() * i) === 0) ans = node.val;
    }
    return ans;
  }
}

class Solution {
    private ListNode head;
    private Random rng = new Random();
    public Solution(ListNode head) { this.head = head; }
    public int getRandom() {
        int ans = head.val, i = 1;
        for (ListNode node = head.next; node != null; node = node.next) {
            i++;
            if (rng.nextInt(i) == 0) ans = node.val;
        }
        return ans;
    }
}

class Solution {
    ListNode* head;
public:
    Solution(ListNode* head) : head(head) {}
    int getRandom() {
        int ans = head->val, i = 1;
        for (ListNode* n = head->next; n; n = n->next) {
            i++;
            if (rand() % i == 0) ans = n->val;
        }
        return ans;
    }
};

Explanation

We want to pick a node uniformly at random, but the list length is unknown and we can only use constant memory — so we can't first count the nodes or store them in an array. The technique that solves this is reservoir sampling.

The idea: keep a single candidate answer ans as you walk the list. At the i-th node (1-indexed), replace ans with this node's value with probability 1/i. The first node starts as the answer with probability 1.

In the code this is if random.randint(1, i) == 1: ans = node.val — a 1/i chance of swapping in the current value. We never look back, so one pass with no extra storage is enough.

Why is every node equally likely? Take node 3 in a list of 5. It is chosen at step 3 with probability 1/3, then must survive steps 4 and 5, which happen with probability (1 - 1/4) and (1 - 1/5). Multiply: (1/3) × (3/4) × (4/5) = 1/5. The same cancellation gives 1/n for every node.

So for 1 → 2 → 3 → 4 → 5, each value comes back with probability exactly 1/5, all in a single linear scan.

Time: O(n) per call Space: O(1)