LeetCode 382: Linked List Random Node Solution in Python – A Step-by-Step Guide

What Is LeetCode 382: Linked List Random Node?

LeetCode 382: Linked List Random Node provides a singly linked list, and your task is to implement a Solution class that can return a random node’s value with uniform probability. You’re given the head of the list during initialization, and getRandom can be called multiple times. It’s a design problem that tests your ability to handle randomness with limited access!

Problem Statement

• Class: Solution
• Methods:
• __init__(head): Initialize with the linked list head.
• getRandom(): Return a random node’s value with equal probability.
• Rules:
• Linked list has at least one node.
• Use only one pass over the list for getRandom.
• Each node has an equal chance (1/n) of being chosen.

Constraints

• Number of nodes: 1 to 10⁴.
• -10⁴ <= Node.val <= 10⁴
• At most 10⁴ calls to getRandom.

Examples

• Input: ["Solution","getRandom","getRandom","getRandom"], [[[1,2,3]],[],[],[]]
• Output: [null,1 or 2 or 3,1 or 2 or 3,1 or 2 or 3]
• Init: 1→2→3.
• getRandom(): 1, 2, or 3 (each 1/3 chance).
• Input: ["Solution","getRandom"], [[[1]],[]]
• Output: [null,1]
• Init: 1, getRandom(): 1 (only option).

These show the random pick—let’s solve it!

Understanding the Problem: Random Node Selection

To tackle LeetCode 382 in Python, we need a class that: 1. Initializes with a linked list head. 2. Returns a random node value with uniform probability (1/n). 3. Operates efficiently without knowing the list length upfront.

A naive approach might store all nodes and pick randomly, but that uses O(n) space. We’ll use:

• Best Solution: Reservoir sampling—O(n) time, O(1) space—optimal and elegant.
• Alternative Solution: List conversion—O(n) time, O(n) space—simple but memory-heavy.

Let’s optimize with the best solution!

Best Solution: Reservoir Sampling

Why This Is the Best Solution

The reservoir sampling approach runs in O(n) time with O(1) space by traversing the list once and maintaining a single “reservoir” value, updating it with a probability that ensures uniformity. It’s the most efficient—meeting the one-pass requirement and minimizing memory while achieving true randomness!

How It Works

Think of it like a lottery with a single winner:

• Reservoir: Start with the first node’s value as the chosen one.
• Traverse: For the ith node (1-based index):
• Keep the current reservoir value with probability (i-1)/i.
• Replace it with the new node’s value with probability 1/i.
• Random: Use random.randint to decide.
• Result: After one pass, the reservoir holds a uniformly random value.

It’s like picking a winner as you go, adjusting odds dynamically!

Step-by-Step Example

For head = 1→2→3:

• Init: Reservoir = 1, i = 1.
• Node 2 (i=2):
• Probability 1/2 to replace: Random [0,1], e.g., 0 → Reservoir = 2 (1/2 chance each for 1, 2).
• Node 3 (i=3):
• Probability 1/3 to replace: Random [0,2], e.g., 2 → Reservoir unchanged (2 or 1), or 0/1 → 3.
• Each has 1/3 chance after full pass.
• Result: 1, 2, or 3 (1/3 probability each).

For head = 1→2:

• Reservoir = 1, i=1.
• i=2: 1/2 chance to stay 1, 1/2 to become 2.
• Result: 1 or 2 (1/2 each).

Code with Explanation

Here’s the Python code using reservoir sampling:

Copy codeimport random

class Solution:
    def __init__(self, head: Optional[ListNode]):
        self.head = head

    def getRandom(self) -> int:
        # Reservoir sampling
        reservoir = self.head.val
        curr = self.head.next
        i = 2  # 1-based index for probability

        while curr:
            # With probability 1/i, replace reservoir
            if random.randint(0, i - 1) == 0:
                reservoir = curr.val
            curr = curr.next
            i += 1

        return reservoir

Explanation

• Lines 5-6: __init__: Store head of linked list.
• Lines 8-17: getRandom:
• Start with head’s value as reservoir.
• Traverse from second node (curr = head.next).
• For ith node, replace reservoir with 1/i probability using random.randint.
• Increment i, move to next node.
• Time: O(n)—single pass through list.
• Space: O(1)—only reservoir and counters.

This is like a random lottery with one winner—light and fast!

Alternative Solution: List Conversion

Why an Alternative Approach?

The list conversion solution runs in O(n) time for initialization and O(1) for getRandom but uses O(n) space by storing all node values in a list during init. It’s simpler—great for small lists or when space isn’t a concern, though it doesn’t meet the one-pass ideal!

How It Works

• Init: Convert linked list to a list.
• GetRandom: Pick random index from list.
• Result: Return value at that index.

Step-by-Step Example

For head = 1→2→3:

• Init: List = [1, 2, 3].
• getRandom:
• Random index [0, 2], e.g., 1 → 2 (1/3 chance each).
• Result: 1, 2, or 3.

For head = 1:

• Init: List = [1].
• getRandom: Return 1.

Code with Explanation

Copy codeimport random

class Solution:
    def __init__(self, head: Optional[ListNode]):
        # Convert linked list to list during initialization
        self.values = []
        curr = head
        while curr:
            self.values.append(curr.val)
            curr = curr.next

    def getRandom(self) -> int:
        # Return random element from list
        return random.choice(self.values)

Explanation

• Lines 5-10: __init__:
• Traverse list, store values in self.values—O(n).
• Lines 12-14: getRandom:
• Use random.choice on list—O(1).
• Time: O(n) init, O(1) getRandom.
• Space: O(n)—stores all values.

It’s a straightforward random picker—memory-heavy!

Comparing the Two Solutions

• Reservoir Sampling (Best):
• Time: O(n) per getRandom—single pass.
• Space: O(1)—minimal.
• Pros: Space-efficient, one-pass.
• Cons: Slightly more complex logic.
• List Conversion (Alternative):
• Time: O(n) init, O(1) getRandom.
• Space: O(n)—list.
• Pros: Simple, fast getRandom.
• Cons: High space, preprocesses all.

Reservoir sampling wins for space and elegance!

Additional Examples and Edge Cases

• Single node: Both return its value.
• Long list: Reservoir scales better in space.
• Repeated calls: Both maintain uniformity.

Reservoir is optimal, list is memory-intensive.

Complexity Breakdown

• Reservoir Sampling:
• Time: O(n) per call.
• Space: O(1).
• List Conversion:
• Time: O(n) init, O(1) per call.
• Space: O(n).

Reservoir excels for space efficiency.

Key Takeaways

• Reservoir Sampling: Random in one pass—lean and smart!
• List Conversion: Store and pick—clear but heavy!
• Randomness: Probability meets constraints.
• Python Tip: Random rocks—see [Python Basics](/python/basics).

Final Thoughts: Pick That Node

LeetCode 382: Linked List Random Node in Python is a randomness challenge. Reservoir sampling is the efficiency champ, while list conversion offers simplicity at a space cost. Want more? Try LeetCode 380: Insert Delete GetRandom O(1) or LeetCode 398: Random Pick Index. Ready to roll? Visit Solve LeetCode 382 on LeetCode and pick that random node today!