Linked List Random Node

This blog series attempts to solve the 500 Top Leet Code Interview Questions with the help of AI Code Assistance, such as Gemini and GPT.

Question 193:

Linked List Random Node

You are given a singly linked list.
You need to return a random node’s value such that each node is equally likely to be selected.
You must not use extra space (like storing the entire list in an array), especially if the list is large or its length is unknown.

Optimal Solution:

We use Reservoir Sampling, a probability-based technique used to select one or more random items from a stream (or list) of unknown size with equal probability.

The idea is simple:

• We iterate through the list only once.
• At each step i, we choose the current node with probability 1/i.

This ensures every node has an equal chance of being selected by the time we reach the end.

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:
        current = self.head
        result = current.val
        index = 1
        
        while current.next:
            current = current.next…