How do you solve Linked List Random Node on LeetCode?

Linked List Random Node (LeetCode #382) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: Reservoir Sampling ensures equal probability for each node.

What is the brute force solution for Linked List Random Node?

The brute force approach for Linked List Random Node is Brute Force, with O(n²) time complexity and O(n) space complexity. In this approach, we traverse the entire linked list to collect all node values into an array. Then, we randomly select an index from this array to return the corresponding value. This is simple but inefficient for large lists. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Linked List Random Node?

Linked List Random Node uses the following concepts: Linked List, Math, Reservoir Sampling, Randomized. The recommended patterns to study are: Reservoir Sampling, Randomized Algorithms.

What are the interview tips for Linked List Random Node?

Explain your thought process clearly. Discuss the trade-offs of each approach. Practice writing code on a whiteboard or in a shared document.

What are common mistakes when solving Linked List Random Node?

Not considering the edge case of a single node. Failing to ensure equal probability in random selection.

#382

Linked List Random Node

Medium

Linked ListMathReservoir SamplingRandomizedReservoir SamplingRandomized Algorithms

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(n)	O(1)

💡

Intuition

Time O(n)Space O(1)

This approach uses Reservoir Sampling, allowing us to select a random node without needing to know the length of the list in advance. It ensures each node has an equal probability of being selected while only traversing the list once.

⚙️

Algorithm

4 steps

1Step 1: Initialize a variable to store the result and a counter to track the current index.
2Step 2: Traverse the linked list. For each node, generate a random integer between 0 and the current index.
3Step 3: If the random integer equals the current index, update the result with the current node's value.
4Step 4: Increment the index and continue until the end of the list.

solution.py17 lines

1# Full working Python code
2import random
3class ListNode:
4    def __init__(self, val=0, next=None):
5        self.val = val
6        self.next = next
7class Solution:
8    def __init__(self, head: ListNode):
9        self.head = head
10    def getRandom(self) -> int:
11        result, current, idx = 0, self.head, 0
12        while current:
13            if random.randint(0, idx) == 0:
14                result = current.val
15            current = current.next
16            idx += 1
17        return result

ℹ

Complexity note: The time complexity is O(n) because we traverse the list once. The space complexity is O(1) since we only use a few variables to keep track of the current node and the result, regardless of the list size.

1Reservoir Sampling ensures equal probability for each node.
2Optimal solution requires only one traversal of the list.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.