Code Implementation

import random

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def __init__(self, head: ListNode):
        self.head = head

    def getRandom(self) -> int:
        # Reservoir Sampling
        result = self.head.val
        node = self.head.next
        i = 2
        while node:
            if random.randrange(i) == 0:
                result = node.val
            node = node.next
            i += 1
        return result
      

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
#include <cstdlib>

class Solution {
public:
    ListNode* head;
    Solution(ListNode* head) {
        this->head = head;
    }
    
    int getRandom() {
        // Reservoir Sampling
        int result = head->val;
        ListNode* node = head->next;
        int i = 2;
        while (node) {
            if (rand() % i == 0) {
                result = node->val;
            }
            node = node->next;
            i++;
        }
        return result;
    }
};
      

import java.util.Random;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    private ListNode head;
    private Random rand;

    public Solution(ListNode head) {
        this.head = head;
        this.rand = new Random();
    }
    
    public int getRandom() {
        int result = head.val;
        ListNode node = head.next;
        int i = 2;
        while (node != null) {
            if (rand.nextInt(i) == 0) {
                result = node.val;
            }
            node = node.next;
            i++;
        }
        return result;
    }
}
      

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

var Solution = function(head) {
    this.head = head;
};

/**
 * @return {number}
 */
Solution.prototype.getRandom = function() {
    let result = this.head.val;
    let node = this.head.next;
    let i = 2;
    while (node) {
        if (Math.floor(Math.random() * i) === 0) {
            result = node.val;
        }
        node = node.next;
        i++;
    }
    return result;
};
      

Problem Description

You are given a singly linked list whose head node is head. You need to implement a class Solution with two methods:

• Solution(ListNode head) - Initializes the object with the head of the linked list.
• getRandom() - Returns a random node's value from the linked list. Each node must have an equal probability of being chosen.

Key constraints:

• All node values are valid and can be returned.
• Each call to getRandom() must select any node uniformly at random.
• You may assume that at least one node exists in the list.
• Do not use extra space proportional to the length of the list if possible.

Thought Process

At first glance, it seems straightforward to select a random node from a linked list if you know its length. If you know the length n, you could generate a random index between 0 and n-1 and traverse the list to that index. However, the problem does not guarantee that you know the length in advance, and it's inefficient to traverse the list twice (once to count, once to select) for each getRandom() call.

A brute-force approach would be to store all node values in an array during initialization, then pick a random index from the array. However, this uses extra space proportional to the list length, which may not be acceptable for very large lists.

To optimize, we need a way to select a random node in a single pass and with constant space. This leads to a classic algorithm called reservoir sampling, which allows us to sample uniformly from a stream (or linked list) when we don't know its length in advance.

Solution Approach

We use the reservoir sampling algorithm to select a random node from the linked list with equal probability, using only constant extra space.

• Initialization: Store the reference to the head of the linked list.
• Reservoir Sampling Process in getRandom():
  1. Start at the head node. Let result be the value of the head node.
  2. Iterate through the linked list node by node, keeping track of the current node number i (starting from 2 for the second node).
  3. For each node, generate a random integer between 0 and i-1. If the random integer is 0, update result to the current node's value.
  4. Continue until the end of the list. Return result.
• Why does this work? At each node, the probability of replacing result with the current node's value is 1/i. This ensures that after traversing the entire list, each node has an equal probability of being chosen.

This method requires only a single pass through the list per getRandom() call, and uses only constant extra space.

Example Walkthrough

Suppose the linked list is: 1 → 2 → 3

1. Start at node 1: result = 1
2. Move to node 2 (i=2):
   • Generate a random number between 0 and 1 (inclusive).
   • If the random number is 0, set result = 2; otherwise, keep result = 1.
3. Move to node 3 (i=3):
   • Generate a random number between 0 and 2 (inclusive).
   • If the random number is 0, set result = 3; otherwise, keep the previous result.
4. At the end, return result. Each node has a 1/3 chance of being picked.

Over many calls to getRandom(), the probability of returning 1, 2, or 3 will be approximately equal.

Time and Space Complexity

• Brute-force approach:
  • Time Complexity: O(n) for initialization (copy to array), O(1) for each getRandom().
  • Space Complexity: O(n) for storing all node values.
• Reservoir Sampling approach (optimized):
  • Time Complexity: O(n) per getRandom() call (must traverse the list each time).
  • Space Complexity: O(1) extra space (no storage proportional to list size).

The optimized approach is preferred when the list can be very large or when memory usage is critical.

Summary

The Linked List Random Node problem is elegantly solved using reservoir sampling, which allows for uniform random selection from a list without needing to know its length or store all values. This approach is efficient in space and simple to implement, relying on probability to ensure fairness. The key insight is that at each node, you update your choice with decreasing probability, guaranteeing that each node is chosen with equal likelihood in a single traversal.