Linked List Random Node - Leetcode Solution

Problem Statement:

Given a singly linked list, return a random node's value from the linked list. Each node must have the same probability of being chosen.

Example 1:

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.

Approach:

The given problem can be solved using the reservoir sampling algorithm. The basic idea behind the reservoir sampling algorithm is to select k samples from n elements, where n is either a very large or an unknown number. In this case, n can be the number of nodes in the linked list, and k can be 1 since we want to return a random node's value.

When the algorithm processes the i-th element in the linked list, it generates a random number between 0 and i (inclusive). If the generated number is 0, the algorithm selects the i-th element as the random sample. Otherwise, the i-th element is included in the sample with a probability of 1/i.

As the algorithm progresses, each element in the linked list has the same probability of being selected as the random sample.

Solution:

We can use the reservoir sampling algorithm to solve the given problem. We can create a helper function to generate a random number between 0 and i (inclusive) and use it to determine whether to update the current random sample in each iteration.

We can maintain two variables:

1. A count variable to keep track of the number of nodes that we have seen so far.
2. A variable to store the value of the current random sample.

In each iteration, we update the count variable and generate a random number between 0 and count (inclusive). If the generated number is 0, we update the random sample variable with the value of the current node's value.

After we have iterated over all nodes in the linked list, the random sample variable will contain the value of the selected random node.

Code in Python:

class Solution:

    def __init__(self, head: ListNode):
        self.head = head

    def getRandom(self) -> int:
        count = 0
        curr = self.head
        random_sample = None
        while curr:
            count += 1
            if random.randint(1, count) == 1:
                random_sample = curr.val
            curr = curr.next
        return random_sample

Time Complexity: The time complexity of the solution is O(N), where N is the number of nodes in the linked list. We iterate through each node in the linked list exactly once.

Space Complexity: The space complexity of the solution is O(1) since we are only using a few constant amount of extra space for variables.

1