Linked List Random Node

Problem Statement

The task is to design a class Solution that allows retrieving random values from a node in a singly-linked list with equal probability for each node. The class should be designed such that it has a constructor that takes the head of the linked list. Another key method, getRandom(), will select a node's value randomly from the linked list ensuring that each node's value has the same likelihood of being chosen. The structure emphasizes randomness and unbiased selection from the linked list's nodes.

Examples

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
Each call to getRandom() should return either 1, 2, or 3 with equal probability.

Constraints

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

Approach and Intuition

Given the challenge to equally likely select a random node from a singly-linked list, a straightforward approach may not work due to the lack of direct access to list nodes by indices as available in arrays. This requirement brings about the necessity for a fair and random selection mechanism for linked list nodes. The getRandom() function, when called, must randomly return any node's value from the entire linked list with uniform selection probability. Let's understand with stages:

1. Initialization:

   • Upon initializing with the Solution class constructor, store the head of the linked list.

2. Random Node Selection:

   • Utilize the Reservoir Sampling algorithm for optimal results especially when linked list length is unknown or extremely large.
   • Traverse through the linked list starting from the head.
   • For each node, decide whether it replaces a previously chosen node in our 'reservoir' (initially the first node is chosen).
   • The probability of keeping the current node value becomes 1/k where k is the current node's index in the list + 1 (considering 1-based index).

   For example, as we advance through each node:

   • The first node gets selected with a probability of 1 (since it’s the only one).
   • For the second node, there’s a 1/2 chance it replaces the first node as the chosen node.
   • For the third node, it has a 1/3 chance, and so forth.
   • This method ensures that by the end of the list, each node has had an equal opportunity to be chosen.

3. Return Value:

   • After completing the traversal with the reservoir sampling method applied, the value stored as the chosen node will be returned each time getRandom() is called.

This approach adheres to the constraint of each node possessing an equal probability of being chosen, given the lack of upfront knowledge about the length of the list or needing to go past the list multiple times which could be computationally expensive. The randomness is maintained uniformly across the nodes by the nature of the sampling method.

Solutions

class Solution {
    private ListNode listHead;

    public Solution(ListNode listHead) {
        this.listHead = listHead;
    }

    public int getRandom() {
        int count = 1, selectedValue = 0;
        ListNode currentNode = this.listHead;
        while (currentNode != null) {
            if (Math.random() < 1.0 / count)
                selectedValue = currentNode.val;
            count += 1;
            currentNode = currentNode.next;
        }
        return selectedValue;
    }
}

class Solution:
    def __init__(self, start_node: ListNode):
        self.start_node = start_node

    def pickRandom(self) -> int:
        count = 1
        selected_value = 0
        node = self.start_node

        while node:
            if random.random() < 1 / count:
                selected_value = node.val
            node = node.next
            count += 1
        return selected_value