We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Linked List Random Node

Number: 382

Difficulty: Medium

Paid? No

Companies: Google, Meta, Nvidia

Problem Description

Given a singly linked list, the task is to implement a data structure that supports choosing a random node's value such that every node in the list has the same probability of being selected, regardless of the list's length. The implementation should support constructing the data structure with the head of the list and a method to return a random node’s value.

Key Insights

  • The main challenge is selecting a node uniformly at random from a linked list without knowing its length in advance.
  • Reservoir Sampling is a perfect algorithm for this problem; it allows sampling from an unknown or very large stream using constant space.
  • Each node is processed sequentially. As you traverse, maintain a candidate result and potentially replace it with the current node based on calculated probability.
  • The probability to choose each node ensures that every node has a 1/N chance, where N is the total number of nodes processed so far.

Space and Time Complexity

Time Complexity: O(n) per call to getRandom, where n is the number of nodes in the list. Space Complexity: O(1) additional space since only a few pointers and counters are used.

Solution

The solution initializes the data structure with the head of the linked list. When getRandom is called, the algorithm uses reservoir sampling. Start with the first node's value as the initial candidate. Then, iterate through the remainder of the list. For each node encountered at index i (starting from 1), generate a random number in the range [0, i] and if the number equals 0, update the candidate. This method guarantees that each node is selected with equal probability. The trick is to note that the i-th node has a 1/(i+1) chance of replacing the current candidate, ensuring uniform randomness for any list size without needing to know the total number of nodes originally.

Code Solutions

import random

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def __init__(self, head):
        # Store the head of the linked list
        self.head = head

    def getRandom(self):
        # Initialize current pointer to the head and set result to None
        current = self.head
        result = None
        count = 0

        # Traverse through the list
        while current:
            count += 1
            # With probability 1/count, select the current node's value
            if random.randrange(count) == 0:
                result = current.val
            current = current.next
        
        return result

# Comments:
# Each node is considered with diminishing probability.
# Reservoir sampling ensures uniform selection without extra space.
← Back to All Questions