{x}
blog image

Linked List Random Node

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.

 

Example 1:

Input
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1, 2, 3]], [], [], [], [], []]
Output
[null, 1, 3, 2, 2, 3]

Explanation
Solution solution = new Solution([1, 2, 3]);
solution.getRandom(); // return 1
solution.getRandom(); // return 3
solution.getRandom(); // return 2
solution.getRandom(); // return 2
solution.getRandom(); // return 3
// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.

 

Constraints:

  • The number of nodes in the linked list will be in the range [1, 104].
  • -104 <= Node.val <= 104
  • At most 104 calls will be made to getRandom.

 

Follow up:

  • What if the linked list is extremely large and its length is unknown to you?
  • Could you solve this efficiently without using extra space?

Solution Explanation

This problem utilizes reservoir sampling to select a random node from a singly linked list with equal probability. Reservoir sampling is a family of algorithms that allows for selecting a sample of k items from a population of unknown size. In this case, k=1.

The algorithm works as follows:

  1. Initialization: We initialize ans (the randomly selected node's value) to 0 and n (the count of nodes processed) to 0. We iterate through the linked list.

  2. Iteration: For each node encountered:

    • Increment n.
    • Generate a random integer x between 1 and n (inclusive). This represents our "selection probability".

  3. Selection: If x is equal to n, this means we've randomly decided to choose the current node's value. Therefore, update ans to be the current node's value.

Why this works:

The probability of selecting any given node is:

  • Node 1: The probability of choosing the first node is 1 (because n will be 1 and x will always be 1).

  • Node i (where i > 1): The probability of selecting node i is the probability that it's not selected before AND that it's selected at iteration i. This is: (1 - 1/2) * (1 - 1/3) * ... * (1 - 1/(i-1)) * (1/i). This simplifies to 1/i.

Time Complexity Analysis:

  • __init__ (constructor): O(1) - Constant time to store the head.
  • getRandom: O(N) - Linear time complexity, where N is the number of nodes in the linked list. This is because we iterate through the entire list in the worst case.

Space Complexity Analysis:

  • O(1) - Constant extra space. We only use a few integer variables.

Code Explanation (Python3)

import random
 
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
class Solution:
    def __init__(self, head: Optional[ListNode]):
        self.head = head
 
    def getRandom(self) -> int:
        n = ans = 0
        head = self.head
        while head:
            n += 1
            x = random.randint(1, n)  # Generate random integer between 1 and n
            if n == x:
                ans = head.val     # Update ans if this node is selected
            head = head.next       # Move to the next node
        return ans

The Python code directly implements the algorithm described above. The random.randint(1, n) function is crucial for the reservoir sampling technique. The rest of the code simply iterates through the linked list and performs the selection logic.

The other languages (Java, C++, Go) follow the same logic, adapting the syntax and random number generation to their specific environments. For example, Java uses java.util.Random, C++ uses rand(), and Go uses rand.Intn(). The core algorithm remains consistent.