Linked List Random Node

Intuitionwhy one changing candidate can represent the entire list

A random answer from a list of one node is forced: keep that node. When the second node arrives, choose between the old candidate and the new node with equal probability. After the third node arrives, the new node should be kept with probability 1/3, while each earlier candidate should survive with probability 2/3. If an earlier node had probability 1/2 before this step, its final probability becomes 1/2 x 2/3 = 1/3.

The same argument continues at every position. When you reach node i, replace the candidate with probability 1/i; otherwise keep it. Every node has probability 1/i of becoming the candidate, and every candidate already in the reservoir has probability (i - 1)/i of surviving. Their probabilities are therefore equal, so after the final node every list node is represented with probability 1/n.

Approachthe one-pass reservoir update

1. 1Keep the first node's value as the initial candidate, because the list is guaranteed to be non-empty and a candidate must exist before any later node can replace it.
2. 2Start at the second node with i = 2, because this is the second possible choice and it must replace the current candidate with probability 1/2.
3. 3For each current node, generate a random integer from 0 through i - 1. This gives one replacement outcome among i equally likely outcomes; using a fixed replacement probability would not keep all nodes equally likely.
4. 4Replace the candidate only when the random integer is 0, because that event has probability 1/i and gives the current node its required share.
5. 5Advance to the next node and increment i, because the next node will be competing with one more possible position.
6. 6Return the candidate after the traversal, because the repeated replacement rule has made it uniformly representative of the entire list.

Complexityone pass and no container for the nodes

Annotated solutionC++ · one pass · reservoir sampling in its smallest form

#include <cstdlib>

using namespace std;

class Solution {
public:
    int getRandom(ListNode* head) {
        int result = head->val;
        ListNode* current = head->next;
        int position = 2;

        while (current != nullptr) {
            int randomValue = rand() % position;
            if (randomValue == 0) {
                result = current->val;
            }

            current = current->next;
            position++;
        }

        return result;
    }
};

The initial candidate handles the first node without needing a random choice. At the second node, position is 2, so randomValue == 0 occurs with probability 1/2. After processing any node, position is incremented before the next iteration, keeping the denominator aligned with the next node's 1-based position. Moving that increment earlier would make every replacement probability use the wrong position.

The two-pass alternativewhen direct random indexing is worth a second traversal

You can first count the nodes, choose a random index in the range 0 to n - 1, and then walk to that index. This is not a space optimisation: it also uses O(1) extra space and O(n) time, but it makes the uniform choice feel more direct. The cost is two traversals instead of one, while reservoir sampling works without ever knowing the length.

#include <cstdlib>

using namespace std;

class Solution {
public:
    int getRandom(ListNode* head) {
        int length = 0;
        ListNode* current = head;

        while (current != nullptr) {
            length++;
            current = current->next;
        }

        int target = rand() % length;
        current = head;
        while (target > 0) {
            current = current->next;
            target--;
        }

        return current->val;
    }
};

Common mistakesthe index and probability errors that look almost right