382. Linked List Random Node – Leetcode Solutions

Example 1:

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

class Solution:
    
    def __init__(self, head: Optional[ListNode]):
        # Initialize the Solution with the head of the linked list
        self.head = head

    def getRandom(self) -> int:
        # Initialize variables for reservoir sampling
        reservoir = -1  # Placeholder for the value of the selected node
        current = self.head  # Start at the head of the list
        n = 0  # Tracks the index of the current node for probability calculation
        
        # Traverse the linked list
        while current:
            n += 1  # Increment the count of nodes seen so far
            # Decide to replace the reservoir with current node's value with probability 1/n
            if random.randint(1, n) == 1:
                reservoir = current.val
            # Move to the next node
            current = current.next
        
        return reservoir  # Return the value of the selected node

class Solution {
private:
    ListNode* head; // Head of the linked list

public:
    // Constructor to initialize the Solution with the head of the linked list.
    Solution(ListNode* head) {
        this->head = head;
    }
    
    // Function to get a random node's value using Reservoir Sampling.
    int getRandom() {
        int result;             // To store the value of the selected node
        int count = 1;          // Counter to track the number of nodes traversed
        
        ListNode* current = head; // Start from the head of the list

        // Traverse the linked list
        while (current != nullptr) {
            // Reservoir sampling probability logic:
            // Replace result with current node's value with probability 1/count.
            if (rand() % count == 0) {
                result = current->val; // Select the current node's value
            }
            
            count++;             // Increment the node counter
            current = current->next; // Move to the next node
        }

        return result; // Return the randomly selected node's value
    }
};

var Solution = function(head) {
    // Initialize the Solution class with the head of the linked list.
    this.head = head;
};

/**
 * Chooses a random node from the linked list and returns its value.
 * Each node must have the same probability of being chosen.
 * @return {number} - The value of the randomly chosen node
 */
Solution.prototype.getRandom = function() {
    let result = null; // Variable to store the result (value of the randomly chosen node)
    let current = this.head; // Start from the head of the linked list
    let index = 0; // Tracks the index of the current node as we traverse the list

    // Traverse the entire linked list
    while (current !== null) {
        // For each node, decide if it should be chosen based on its probability
        // Probability of choosing the current node decreases as the index increases
        if (Math.floor(Math.random() * (index + 1)) === 0) {
            result = current.val; // Select the current node's value as the result
        }

        // Move to the next node in the list
        current = current.next;
        index++; // Increment the index for the next node
    }

    return result; // Return the value of the randomly chosen node
};

class Solution {
    // Instance variable to hold the head of the linked list
    private ListNode head;
    // Random object to generate random numbers
    private Random rand;

    /**
     * Constructor to initialize the object with the head of the singly-linked list.
     * @param head the head of the linked list.
     */
    public Solution(ListNode head) {
        this.head = head; // Save the head of the list
        this.rand = new Random(); // Initialize Random object
    }
    
    /**
     * Chooses a random node's value from the linked list.
     * @return the value of the randomly selected node.
     */
    public int getRandom() {
        int result = 0; // Variable to store the result
        ListNode current = head; // Start with the head node
        int count = 0; // Counter to keep track of the node index
        
        // Traverse through the linked list
        while (current != null) {
            count++; // Increment node count
            
            // Generate a random number in the range [0, count-1]
            // If it's 0, update the result with the current node's value
            if (rand.nextInt(count) == 0) {
                result = current.val;
            }
            
            // Move to the next node
            current = current.next;
        }
        
        return result; // Return the randomly selected node's value
    }
}