382. Linked List Random Node

MediumReservoir SamplingLinked ListMathRandomized
Leetcode Link

Problem Description

The problem defines a scenario in which you are given a singly linked list, and you are required to implement a method that returns the value of a random node from that linked list. Importantly, each node in the list should have an equal chance of being chosen. This is achieved by implementing two functions within a Solution class:

  • Solution(ListNode head): A constructor that initializes an instance of the Solution class with the given singly linked list's head.
  • int getRandom(): A function that, when called, should return the value of a randomly chosen node from the linked list, ensuring each node has the same probability of being selected.

Intuition

To solve this problem, we need a method that not only selects a node at random but also ensures each node has an equal chance of being chosen. This problem is known as "reservoir sampling," which is especially useful when the size of the data is unknown or is too large to fit into memory.

The solution provided follows the reservoir sampling algorithm. The intuition behind reservoir sampling is as follows:

  1. Iterate over each node in the given linked list while keeping track of the current node index/counter.
  2. On visiting each node, generate a random number between 1 and the current node's index (inclusive).
  3. If the generated random number equals the current node's index, we select the current node's value as the candidate answer.
  4. Continue this process until the end of the list. Once the end is reached, the value selected will be from one of the nodes, and each node would have had an equal chance of being chosen.

The reason this works is that at each step, the probability of keeping the existing item is equal to the probability of replacing it with the current item, which maintains the uniform random selection of the items. In each iteration, the probability of choosing a node is 1 over the number of nodes encountered so far, thus ensuring the same probability for each node.

Learn more about Linked List and Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Breadth first search can be used to find the shortest path between two nodes in a directed graph.

Solution Approach

The implementation of the Solution class uses the reservoir sampling algorithm to address the challenge of equally likely node selection from the linked list. Let's walk through the steps of the approach:

  1. The __init__ function simply stores the reference to the head of the linked list in the self.head variable. No other initial processing or storage is needed, making initialization straightforward.
1def __init__(self, head: Optional[ListNode]):
2    self.head = head
  1. The getRandom function is where the reservoir sampling algorithm is applied. Let's examine it step-by-step:
1def getRandom(self) -> int:
2    n = ans = 0
3    head = self.head
4    while head:
5        n += 1
6        x = random.randint(1, n)
7        if n == x:
8            ans = head.val
9        head = head.next
10    return ans
  • A variable n is used to keep track of the number of nodes that have been processed (essentially it's the current node's index).
  • A variable ans is used to store the current answer, which is the value of the randomly chosen node.
  • We start a loop that continues until it reaches the end of the linked list (head being None).
  • For each node encountered, we increase n by 1.
  • We then call random.randint(1, n) to generate a random number between 1 and n (inclusive).
  • If the generated random number x equals n (which is the current index of the node), we update ans with the current node's value. The probability of x being equal to n is 1 / n, which corresponds to the probability of selecting any one node when there are n nodes.
  • We move the pointer head to the next node in the list.
  • After the entire list has been traversed, the value accumulated in ans is returned. Due to the probabilities involved in the selection process, this value is the randomly selected node's value with a uniform distribution.

In summary, the algorithm uses a linear scan of the list with a randomness-driven decision made at each node visited to either replace the current selection or continue with the existing one. The random number determines this replacement in accordance with reservoir sampling, requiring no auxiliary data structure, thus achieving optimal space complexity.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

In a binary min heap, the maximum element can be found in:

Example Walkthrough

Let's consider a linked list of 5 nodes with values from 1 to 5. Here is how the Solution class would select a random node using the reservoir sampling technique:

  1. Construct the Solution with the head of the linked list.
  2. Call getRandom() to select a random node. The selection process is as follows:
    • Start with n = 0 and ans = 0.
    • Visit the first node (value = 1): n=1. Generate a random number x between 1 and 1 (random.randint(1, n)). Since x will always be 1 (as that's the only possibility), set ans to the value of this node (1).
    • Visit the second node (value = 2): n=2. Generate a random number x between 1 and 2. If x is 2, set ans to 2. Otherwise, ans remains 1.
    • Visit the third node (value = 3): n=3. Generate a random number x between 1 and 3. If x is 3, set ans to 3, replacing the older value. If not, ans stays the same.
    • Visit the fourth node (value = 4): n=4. Generate a random number between 1 and 4. If x is 4, ans becomes 4. If not, no change.
    • Visit the fifth node (value = 5): n=5. Generate a random number between 1 and 5. If x is 5, ans changes to 5. If not, ans does not change.

After visiting all nodes, ans will hold the value of a node that has been randomly selected, adhering to the requirement that each node has an equal chance (1/5 in this case) of being chosen. Since complete traversal is necessary, each node's probability of being the final answer is even, ensuring the randomness of the process.

Solution Implementation

1import random
2
3# Definition for a singly-linked list node.
4class ListNode:
5    def __init__(self, val=0, next=None):
6        self.val = val
7        self.next = next
8
9class Solution:
10
11    # Constructor which initializes the list head.
12    def __init__(self, head: Optional[ListNode]):
13        self.head = head
14
15    # Returns a random node's value from the linked list.
16    def getRandom(self) -> int:
17        # counter to keep track of the total nodes visited so far
18        count_nodes = 0
19        # variable to store the randomly selected node's value
20        selected_value = None
21        # iterate from the head of the linked list
22        current_node = self.head
23      
24        # Traverse through the list
25        while current_node:
26            count_nodes += 1  # increment the counter for each node
27            # generate a random number between 1 and the current node count
28            random_number = random.randint(1, count_nodes)
29            # if random number equals the current node index, update the selected value
30            if random_number == count_nodes:
31                selected_value = current_node.val
32            # move to the next node
33            current_node = current_node.next
34
35        # Return the randomly selected node's value
36        return selected_value
37
38# The following instantiation and method calls are used to operate on the 'Solution' class:
39# obj = Solution(head)
40# param_1 = obj.getRandom()
41
1import java.util.Random;
2
3// Definition for singly-linked list.
4class ListNode {
5    int val;
6    ListNode next;
7  
8    ListNode() {}
9  
10    ListNode(int val) {
11        this.val = val;
12    }
13  
14    ListNode(int val, ListNode next) {
15        this.val = val;
16        this.next = next;
17    }
18}
19
20class Solution {
21    private ListNode head;
22    private Random randomGenerator = new Random();
23
24    // Constructor which initializes the head of the linked list.
25    public Solution(ListNode head) {
26        this.head = head;
27    }
28
29    // Function to return a random node's value from the linked list.
30    public int getRandom() {
31        int randomValue = 0; // This will store the randomly-selected node's value.
32        int i = 0; // This counter will keep track of the number of nodes traversed so far.
33      
34        // Iterate through the linked list to select a random node.
35        for (ListNode currentNode = head; currentNode != null; currentNode = currentNode.next) {
36            i++; // Increment the count of nodes visited.
37            int randomNumber = 1 + randomGenerator.nextInt(i); // Generate a random number between 1 and i.
38          
39            // If the generated random number equals the number of nodes visited, update the answer.
40            if (i == randomNumber) {
41                randomValue = currentNode.val;
42            }
43        }
44      
45        return randomValue; // Return the randomly-selected node's value.
46    }
47}
48
49// The following class simulates the way the Solution object would be instantiated and called in a client code:
50class Example {
51    public static void main(String[] args) {
52        ListNode listHead = new ListNode(1); // Create a sample linked list.
53        listHead.next = new ListNode(2);
54        listHead.next.next = new ListNode(3);
55
56        Solution solution = new Solution(listHead); // Instantiate the Solution object with the linked list.
57        int randomNodeValue = solution.getRandom(); // Call the getRandom method.
58        System.out.println("Random node's value: " + randomNodeValue);
59    }
60}
61
1#include <cstdlib> // For `rand()`
2
3struct ListNode {
4    int val;
5    ListNode *next;
6    ListNode(int x = 0, ListNode *next = nullptr) : val(x), next(next) {}
7};
8
9class Solution {
10public:
11    ListNode* head; // Pointer to the head of the linked list.
12
13    // Constructor
14    Solution(ListNode* head) {
15        this->head = head;
16    }
17
18    // Returns a random node's value from the linked list.
19    int getRandom() {
20        int scope = 0; // Represents the number of nodes seen so far.
21        int chosenValue = 0; // Value of the randomly chosen node.
22      
23        // Initialize a moving pointer to traverse the linked list.
24        ListNode* currentNode = head;
25      
26        // Traverse the entire list.
27        while (currentNode != nullptr) {
28            scope += 1; // Increase the scope since we are seeing a new node.
29          
30            // Generate a random number in [1, scope] range.
31            int randomNumber = 1 + rand() % scope;
32          
33            // With probability 1/scope, choose the current node's value.
34            if (randomNumber == scope) {
35                chosenValue = currentNode->val;
36            }
37          
38            // Move to the next node in the list.
39            currentNode = currentNode->next;
40        }
41      
42        // Return the chosen value.
43        return chosenValue;
44    }
45};
46
47/**
48 * How to use the Solution class:
49 * 
50 * ListNode* head = new ListNode(1); 
51 * head->next = new ListNode(2);
52 * head->next->next = new ListNode(3);
53 * Solution* solution = new Solution(head);
54 * int randomValue = solution->getRandom(); // Gets a random value from the list.
55 */
56
1class ListNode {
2  val: number;
3  next: ListNode | null;
4
5  constructor(val: number = 0, next: ListNode | null = null) {
6    this.val = val;
7    this.next = next;
8  }
9}
10
11let head: ListNode | null; // Global variable pointing to the head of the linked list
12
13// Function to initiate the list with a head node
14function createList(headValue: number): ListNode {
15  head = new ListNode(headValue);
16  return head;
17}
18
19// Function to add a node to the linked list
20function addNode(newValue: number) {
21  let newNode = new ListNode(newValue);
22  if (head === null) {
23    head = newNode;
24  } else {
25    let current = head;
26    while (current.next !== null) {
27      current = current.next;
28    }
29    current.next = newNode;
30  }
31}
32
33// Function that returns a random node's value from the linked list
34function getRandom(): number {
35  let scope = 0; // Represents the number of nodes seen so far
36  let chosenValue = 0; // Value of the randomly chosen node
37  let currentNode = head; // Initialize a moving pointer to traverse the linked list
38
39  // Traverse the entire list
40  while (currentNode !== null) {
41    scope += 1; // Increase the scope as we see a new node
42
43    // Generate a random number in [1, scope] range
44    let randomNumber = 1 + Math.floor(Math.random() * scope);
45
46    // With probability 1/scope, choose the current node's value
47    if (randomNumber === scope) {
48      chosenValue = currentNode.val;
49    }
50
51    // Move to the next node in the list
52    currentNode = currentNode.next;
53  }
54
55  // Return the chosen value
56  return chosenValue;
57}
58
59/**
60 * How to use the getRandom function:
61 * 
62 * head = createList(1);     // Initializes the list with the head node
63 * addNode(2);               // Adds a node with value 2
64 * addNode(3);               // Adds a node with value 3
65 * let randomValue = getRandom(); // Gets a random value from the list
66 */
67
Not Sure What to Study? Take the 2-min Quiz：

Which technique can we use to find the middle of a linked list?

Time and Space Complexity

The given Python class implements a method to randomly get an element from a singly-linked list.

Time Complexity

The getRandom() method has a time complexity of O(n). This is because it processes each node in the singly-linked list exactly once in a sequential manner. The variable n represents the total number of nodes in the list. The while loop iterates over all n nodes, performing a constant amount of work for each node (generating a random number and performing a comparison).

Space Complexity

The getRandom() method has a space complexity of O(1). The extra space used by the method does not depend on the size of the input linked list. The variables n, ans, head, and x use a constant amount of space regardless of the number of nodes in the list.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

How many ways can you arrange the three letters A, B and C?

Recommended Readings

Linked List Cycle

Linked List Cycle Given a linked list with potentially a loop determine whether the linked list from the first node contains a cycle in it For bonus points do this with constant space Parameters nodes The first node of a linked list with potentially a loop Result Whether there is a loop contained

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫