#382

Medium

auto_awesomeLinked-list pointer manipulation

LeetCode Problem Workspace

Linked List Random Node

Select a random node from a singly linked list ensuring uniform probability using efficient pointer techniques and reservoir sampling.

linked list math reservoir sampling randomized

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

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

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.

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.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def __init__(self, head: Optional[ListNode]):
        self.head = head

    def getRandom(self) -> int:
        n = ans = 0
        head = self.head
        while head:
            n += 1
            x = random.randint(1, n)
            if n == x:
                ans = head.val
            head = head.next
        return ans


# Your Solution object will be instantiated and called as such:
# obj = Solution(head)
# param_1 = obj.getRandom()

Continue Practicing

#398 random pick index #497 random point in non overlapping rectangles #519 random flip matrix