382. Linked List Random Node
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 theSolution
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:
- Iterate over each node in the given linked list while keeping track of the current node index/counter.
- On visiting each node, generate a random number between 1 and the current node's index (inclusive).
- If the generated random number equals the current node's index, we select the current node's value as the candidate answer.
- 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.
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:
- The
__init__
function simply stores the reference to the head of the linked list in theself.head
variable. No other initial processing or storage is needed, making initialization straightforward.
1def __init__(self, head: Optional[ListNode]):
2 self.head = head
- 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
beingNone
). - For each node encountered, we increase
n
by 1. - We then call
random.randint(1, n)
to generate a random number between1
andn
(inclusive). - If the generated random number
x
equalsn
(which is the current index of the node), we updateans
with the current node's value. The probability ofx
being equal ton
is1 / n
, which corresponds to the probability of selecting any one node when there aren
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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:
- Construct the
Solution
with the head of the linked list. - Call
getRandom()
to select a random node. The selection process is as follows:- Start with
n = 0
andans = 0
. - Visit the first node (value = 1):
n=1
. Generate a random numberx
between 1 and 1 (random.randint(1, n)
). Sincex
will always be1
(as that's the only possibility), setans
to the value of this node (1). - Visit the second node (value = 2):
n=2
. Generate a random numberx
between 1 and 2. Ifx
is 2, setans
to 2. Otherwise,ans
remains 1. - Visit the third node (value = 3):
n=3
. Generate a random numberx
between 1 and 3. Ifx
is 3, setans
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. Ifx
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. Ifx
is 5,ans
changes to 5. If not,ans
does not change.
- Start with
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
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.
Which of the following problems can be solved with backtracking (select multiple)
Recommended Readings
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 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 Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.