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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Linked List Random Node

Difficulty: Medium

Problem Description

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 with methods to initialize the object with the head of the linked list and to choose a random node.

Key Insights

  • Use of Reservoir Sampling to ensure that each node has an equal chance of being selected.
  • The solution should efficiently handle a linked list of unknown size.
  • The getRandom function should be able to return a value in constant time.

Space and Time Complexity

Time Complexity: O(n) for the initialization, O(1) for getRandom
Space Complexity: O(1) - no extra space used for storing nodes, only a few variables.

Solution

The problem can be solved using a technique known as Reservoir Sampling. This approach allows us to randomly select a node from a potentially large linked list without needing to know its length beforehand. The algorithm works as follows:

  1. Initialize a variable to keep track of the current node and another for the result.
  2. Iterate through the linked list while maintaining a probability that ensures each node is equally likely to be chosen.
  3. For each node encountered, generate a random number to determine if it should replace the current result.
  4. By the time the end of the list is reached, the result variable will contain a randomly selected node's value.

Code Solutions

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:
        current = self.head
        result = current.val
        n = 1
        
        while current:
            if random.randint(0, n - 1) == 0:  # 1/n chance to select the current node
                result = current.val
            current = current.next
            n += 1
            
        return result
← Back to All Questions