How to Solve Linked List Random Node

This problem requires returning a random node's value from a singly linked list where each node must have equal selection probability. A direct traversal combined with reservoir sampling or counting nodes and indexing ensures uniform randomness. Key strategies involve careful pointer updates and managing probabilities efficiently to avoid bias during multiple getRandom calls.

Problem Statement

You are given a singly linked list and must implement a class that can return a random node's value such that every node has the same probability of being chosen. The list can be of any length within the constraints, and the selection should remain uniform even with repeated calls.

Implement a Solution class with a constructor that receives the head of the linked list, and a getRandom method that returns a random node's value. Ensure your method can handle up to 10^4 calls efficiently without introducing bias, using techniques suitable for linked-list pointer manipulation and reservoir sampling.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

Input ["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"] [[[1, 2, 3]], [], [], [], [], []] Output [null, 1, 3, 2, 2, 3]

Explanation Solution solution = new Solution([1, 2, 3]); solution.getRandom(); // return 1 solution.getRandom(); // return 3 solution.getRandom(); // return 2 solution.getRandom(); // return 2 solution.getRandom(); // return 3 // getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.

Constraints

• The number of nodes in the linked list will be in the range [1, 104].
• -104 <= Node.val <= 104
• At most 104 calls will be made to getRandom.

Solution Approach

Reservoir Sampling Approach

Traverse the linked list once while maintaining a single selected value. For each node at index i, replace the selected value with the current node's value with probability 1/(i+1). This ensures uniform randomness and works without knowing the total length in advance.

Counting and Indexing Method

First traverse the linked list to count total nodes. Then generate a random integer in [0, count-1] and iterate to that index to return the node's value. This method uses extra traversal but avoids probability miscalculations inherent in pointer updates.

Optimized Pointer Management

Maintain a current pointer and a counter to track node positions during repeated getRandom calls. Update the selection only as needed and reset counters appropriately to prevent bias. This reduces unnecessary list traversals and handles repeated random access efficiently.

Complexity Analysis

Time complexity is O(N) for initial traversal or O(1) per getRandom call with reservoir sampling if counting is done incrementally. Space complexity is O(1) if only pointers and counters are stored, avoiding extra arrays.

What Interviewers Usually Probe

• Check if you can implement getRandom without storing all node values in an array.
• Expect discussion on uniform probability correctness with repeated calls.
• Look for use of reservoir sampling or careful pointer updates instead of naïve selection.

Common Pitfalls or Variants

Common pitfalls

• Replacing selected value incorrectly with wrong probability, causing biased selection.
• Assuming linked list length is known without counting, leading to index errors.
• Using extra space unnecessarily instead of O(1) pointer-based methods.

Follow-up variants

• Return k random nodes from a linked list with uniform probability.
• Support modifications to the linked list between getRandom calls while maintaining uniform selection.
• Implement a weighted random selection where nodes have different probabilities based on their values.

How GhostInterview Helps

• Provides step-by-step reservoir sampling implementation tailored to linked lists.
• Highlights pointer management techniques to avoid common selection bias mistakes.
• Simulates repeated getRandom calls to verify uniform probability across nodes.

Topic Pages

• Linked List
• Math
• Reservoir Sampling
• Randomized

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

How does Linked List Random Node ensure uniform probability?

It uses reservoir sampling or indexed traversal where each node has a 1/N chance of being selected, ensuring no node is favored.

Can getRandom be optimized for repeated calls?

Yes, by maintaining a pointer and counter, you can minimize traversal while keeping probability uniform.

Is extra space required to store nodes for random selection?

No, efficient solutions use O(1) space by updating a selected value during traversal instead of storing all nodes.

What common mistakes occur with reservoir sampling in linked lists?

Mistakes include updating the selected node with incorrect probability or resetting counters improperly, leading to biased selection.

Can this method handle very large linked lists?

Yes, reservoir sampling allows selecting a random node in a single pass without preloading all nodes, making it scalable.