algoadvance

Leetcode 382. Linked List Random Node

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.

Implement the Solution class:

• Solution(ListNode head) Initializes the object with the head of the singly-linked list head.
• int getRandom() Chooses a node randomly from the list and returns its value. All the nodes of the list should be equally likely to be chosen.

Clarifying Questions

1. Input Constraints:
   • How long can the linked list be? (It can be reasonably long)
   • What are the possible values for the node’s data? (It can be any integer)
2. Randomness Requirements:
   • Is there any specific random number generator we should use? (We can use C++ standard library).
3. Edge Cases:
   • What should we do if the list is empty? (We can assume the list is non-empty).

Strategy

1. Initialization:
   • Store the head of the list.
2. Solution Approach:
   • To ensure each node is picked with equal probability, we can use Reservoir Sampling.
   • Traverse the list. For the i-th node, select it with probability 1/i.
3. Algorithm:
   • Initialize a variable to store the chosen value.
   • Start with the head node, and initialize a counter.
   • Traverse through the linked list:
     • For each node with index i:
       • Generate a random number between 1 and i.
       • If the generated number is 1, update the chosen value to the current node’s value.
   • Continue until you traverse through the entire list.
   • Return the chosen value.

Code

Here is the implementation of the above approach in C++:

#include <cstdlib> // For rand() and srand()
#include <ctime>   // For time()

// Definition for singly-linked list node.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* head;
    
    // Initialize with head of the linked list.
    Solution(ListNode* head) {
        this->head = head;
        std::srand(std::time(nullptr)); // Seed for randomness
    }
    
    int getRandom() {
        ListNode* current = head;
        int result = current->val;
        int index = 1;
        while (current != nullptr) {
            // Generate a random number between 1 and index (both inclusive)
            if (std::rand() % index == 0) {
                result = current->val;
            }
            index++;
            current = current->next;
        }
        return result;
    }
};

Time Complexity

• Initialization (Constructor): O(1) - Just store the head of the list.
• getRandom() Method: O(N) - Traverse through the entire list where N is the number of nodes in the list.

This ensures each node is picked with equal probability, making it an effective and efficient approach for the problem.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?