Problem Description

This problem asks you to implement a data structure that can randomly select a value from a linked list where each node has an equal probability of being chosen.

You need to create a Solution class with two methods:

1. Constructor __init__(self, head): Takes the head of a singly-linked list and initializes the object with it.

2. Method getRandom(): Returns a random node's value from the linked list. The key requirement is that every node must have the same probability of being selected.

The challenge here is that with a linked list, you don't know the total length beforehand (unlike an array where you can directly access any element by index). The solution uses Reservoir Sampling, a technique for randomly choosing k items from a list of unknown size.

The algorithm works as follows:

• Start with a counter n = 0 and traverse the linked list
• For each node encountered:
  • Increment the counter n
  • Generate a random number between 1 and n
  • If the random number equals n, update the answer to the current node's value
• After traversing the entire list, return the stored answer

This ensures that each node has a probability of 1/n of being selected, where n is the total number of nodes. The mathematical proof: for the i-th node to be selected, it needs to be chosen when encountered (probability 1/i) and not replaced by any subsequent nodes (probability (i)/(i+1) * (i+1)/(i+2) * ... * (n-1)/n), which simplifies to 1/n.

Intuition

The first thought might be to traverse the linked list once to count all nodes, then generate a random number between 1 and the total count, and traverse again to get that specific node. However, this requires two passes through the list.

Can we do it in a single pass? This is where the clever insight comes in.

Imagine you're reading through a book page by page, but you don't know how many pages there are. You want to randomly select one page such that every page has an equal chance of being chosen. How would you do it?

The key insight is to use a "replacement strategy". As you go through each element:

• When you see the 1st element, select it with probability 1/1 = 1 (definitely select it since it's the only one so far)
• When you see the 2nd element, select it with probability 1/2 (replace the first one with 50% chance)
• When you see the 3rd element, select it with probability 1/3 (replace the current selection with 33.3% chance)
• And so on...

This way, at any point during traversal, each element seen so far has an equal probability of being the current selection. When you reach the end, every element has had exactly 1/n probability of being the final selection.

The beauty of this approach is that you don't need to know the total count beforehand. You make the decision for each element as you encounter it, using only the information about how many elements you've seen so far. This technique, known as Reservoir Sampling, elegantly solves the problem in a single pass with O(1) space complexity (not counting the input list).

Solution Approach

The implementation uses the Reservoir Sampling algorithm to achieve uniform random selection in a single pass through the linked list.

Implementation Details:

1. Initialization (__init__ method):

   • Store the head of the linked list as an instance variable
   • This allows the getRandom method to traverse the list from the beginning each time it's called

2. Random Selection (getRandom method):

   • Initialize two variables:
     • n = 0: Counter for the current position in the list
     • ans = 0: Variable to store the selected node's value
   • Start traversing from the head of the linked list

3. Core Algorithm Loop:

   while head:
       n += 1
       x = random.randint(1, n)
       if n == x:
           ans = head.val
       head = head.next

   For each node in the list:

   • Increment the counter n (now we've seen n nodes)
   • Generate a random integer x between 1 and n (inclusive)
   • If x equals n, update ans with the current node's value
     • This gives the current node a probability of 1/n to be selected
   • Move to the next node

4. Return Result:

   • After traversing the entire list, return ans which holds the randomly selected value

Why This Works:

The condition if n == x means we're replacing the current answer with probability 1/n. For the i-th node:

• It gets selected when we reach it with probability 1/i
• It remains selected (not replaced) by node i+1 with probability (i)/(i+1)
• It remains selected by node i+2 with probability (i+1)/(i+2)
• And so on until the last node

The final probability = 1/i × i/(i+1) × (i+1)/(i+2) × ... × (n-1)/n = 1/n

This telescoping product ensures each node has exactly 1/n probability of being the final selection, achieving uniform randomness.

Example Walkthrough

Let's walk through the Reservoir Sampling algorithm with a small linked list: [10] -> [20] -> [30] -> null

We want to understand how getRandom() ensures each node has equal probability (1/3) of being selected.

Step-by-step execution:

Initial state:

• n = 0 (counter for nodes seen)
• ans = 0 (stores selected value)
• head points to first node [10]

Step 1: Process node [10]

• Increment n = 1
• Generate random number x between 1 and 1: x = 1
• Check: Is n == x? Yes (1 == 1)
• Update ans = 10
• Move to next node [20]
• Current selection: 10 (probability 1/1 = 100%)

Step 2: Process node [20]

• Increment n = 2
• Generate random number x between 1 and 2: let's say x = 2
• Check: Is n == x? Yes (2 == 2)
• Update ans = 20
• Move to next node [30]
• Current selection: 20 (replaced 10 with 50% chance)

Step 3: Process node [30]

• Increment n = 3
• Generate random number x between 1 and 3: let's say x = 1
• Check: Is n == x? No (3 ≠ 1)
• Keep ans = 20 (no update)
• Move to next node (null)
• Current selection: still 20 (30 had 1/3 chance but wasn't selected)

Result: Return ans = 20

Probability verification: Let's verify that each node truly has 1/3 probability:

• Node [10]: Selected when n=1 (probability 1), kept when n=2 (probability 1/2), kept when n=3 (probability 2/3)

  • Final probability: 1 × 1/2 × 2/3 = 1/3 ✓

• Node [20]: Selected when n=2 (probability 1/2), kept when n=3 (probability 2/3)

  • Final probability: 1/2 × 2/3 = 1/3 ✓

• Node [30]: Selected when n=3 (probability 1/3)

  • Final probability: 1/3 ✓

Each node has exactly 1/3 chance of being the final answer, demonstrating uniform random selection!

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the number of nodes in the linked list.

• The __init__ method takes O(1) time as it only stores a reference to the head node.
• The getRandom method traverses the entire linked list once, visiting each node exactly once. For each node visited, it performs constant time operations (incrementing counter, generating random number, conditional assignment). Therefore, the time complexity is O(n).

Space Complexity: O(1)

• The __init__ method uses O(1) space to store the head reference.
• The getRandom method uses only a constant amount of extra space for variables n, ans, head, and x, regardless of the size of the linked list. It doesn't create any additional data structures that scale with input size.
• This implementation uses Reservoir Sampling algorithm which maintains constant space complexity while ensuring each node has an equal probability 1/n of being selected.

Common Pitfalls

1. Modifying the Original Linked List Head

A critical mistake is directly using self.head for traversal in getRandom():

Incorrect Implementation:

def getRandom(self) -> int:
    n = 0
    ans = 0
    while self.head:  # WRONG: This modifies self.head!
        n += 1
        x = random.randint(1, n)
        if n == x:
            ans = self.head.val
        self.head = self.head.next  # After this, self.head points to next node
    return ans

Problem: After the first call to getRandom(), self.head becomes None, and subsequent calls will fail or return 0.

Solution: Always use a temporary variable to traverse:

def getRandom(self) -> int:
    current = self.head  # Create a copy of the reference
    n = 0
    ans = 0
    while current:
        n += 1
        x = random.randint(1, n)
        if n == x:
            ans = current.val
        current = current.next
    return ans

2. Using Wrong Random Number Comparison

Some implementations mistakenly use if x == 1 instead of if x == n:

Incorrect:

if x == 1:  # WRONG: This gives early nodes higher probability
    ans = current.val

Correct:

if x == n:  # Or equivalently: if x == count
    ans = current.val

The condition x == n (or any fixed number between 1 and n) ensures 1/n probability for selection.

3. Off-by-One Errors in Random Generation

Using random.randint(0, n-1) or random.randrange(n) requires different comparison logic:

If using 0-indexed random:

x = random.randint(0, n-1)  # Generates 0 to n-1
if x == 0:  # Must compare with 0, not n
    ans = current.val

Consistency is key - stick to one approach throughout your implementation.

4. Storing All Nodes in Memory

While tempting for simplicity, storing all nodes defeats the purpose of Reservoir Sampling:

Memory-Inefficient Approach:

def __init__(self, head):
    self.nodes = []
    while head:
        self.nodes.append(head.val)
        head = head.next

def getRandom(self):
    return random.choice(self.nodes)

Problem: This uses O(n) extra space and doesn't demonstrate understanding of the streaming/reservoir sampling technique, which is designed for scenarios where you can't store all data in memory.