Linked List Random Node solution and explanation
Google
9 more videos on this problem
Linked List Random Node - (Leetcode - 382) - (GOOGLE) : Explanation ➕ Live CodingcodestorywithMIK · 21:14 · 16K views
Linked List Random Node 🔥 | Leetcode 382 | Linked ListAyushi Sharma · 6:01 · 6K views
Linked List Random Node | Live Coding with Explanation | Leetcode - 382Algorithms Made Easy · 7:49 · 6K views
Linked List Random Node | Leetcode 382| Live coding session 🔥🔥🔥 | | Reservoir sampling Algorithm 💯💯Coding Decoded · 14:18 · 2K views
Linked List Random Node || Reservoir Sampling || Interview Question || Leetcode-382Aryan Mittal · 20:15 · 2K views
Linked List Random Node | Leet code 382 | Theory explained + Python codeSai Anish Malla · 14:26 · 2K views
382. Linked List Random Node | LeetCode Daily Challenge | LeetCode POTDDeep Tech · 14:26 · 1K views
Daily Leetcode #1074: Mar 10, 2023 - 382. Linked List Random NodeProgramming Live with Larry · 8:05 · 1K views
Linked List Random Node - Leetcode 382 - PythonTechError · 6:01 · 1K views
Daily Leetcode #246: Dec 02, 2020 - 382. Linked List Random NodeProgramming Live with Larry · 12:48 · 668 views
The problem
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 listhead.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.
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 // getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.
Constraints:
- The number of nodes in the linked list will be in the range
[1, 104]. -104 <= Node.val <= 104- At most
104calls will be made togetRandom.
Follow up:
- What if the linked list is extremely large and its length is unknown to you?
- Could you solve this efficiently without using extra space?
Approach overview
Problem Overview: You receive the head of a singly linked list and must implement getRandom() so that every node value has the same probability of being returned. The challenge is that the list length may be unknown, and the structure only allows sequential traversal.
Approach 1: Preprocessing with Array (Time: O(1) per query, Space: O(n))
Traverse the linked list once during initialization and copy every node value into an array. When getRandom() is called, generate a random index between 0 and n-1 and return the value at that position. Array indexing is constant time, so each query is extremely fast. The trade‑off is memory usage: storing all node values requires O(n) extra space.
This approach works well when the list size is moderate and getRandom() is called many times. The one‑time preprocessing cost amortizes nicely across repeated queries.
Approach 2: Reservoir Sampling (Time: O(n) per query, Space: O(1))
When extra memory is restricted or the list length is unknown, use reservoir sampling. Iterate through the list while maintaining a candidate result. For the first node, select it as the current answer. For each subsequent node at position i, replace the stored value with probability 1/i. This probability rule guarantees that every node has equal probability of being chosen after the traversal finishes.
The algorithm works because each element survives the replacement process with equal likelihood. Only one variable stores the current candidate, so space remains constant. This method belongs to the family of randomized algorithms designed for streaming or unknown‑size data.
Recommended for interviews: Reservoir Sampling. Interviewers typically expect this solution because it demonstrates understanding of probability and algorithms for streaming data. The array preprocessing approach shows practical thinking, but the reservoir technique proves you know how to maintain uniform randomness without storing the entire dataset.
Approach 1: Approach 1: Preprocessing with Array
This method involves converting the linked list into an array during the initialization of the Solution object. Once the linked list is stored as an array, we can easily obtain a random node's value by selecting a random index in the array. This guarantees each node has an equal probability of being chosen.
import random
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def __init__(self, head: ListNode):
self.values = []
node = head
while node:
self.values.append(node.val)
node = node.next
def getRandom(self) -> int:
return random.choice(self.values)import java.util.ArrayList;
import java.util.Random;
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
class Solution {
private ArrayList<Integer> values;
private Random rand;
public Solution(ListNode head) {
values = new ArrayList<>();
rand = new Random();
ListNode node = head;
while (node != null) {
values.add(node.val);
node = node.next;
}
}
public int getRandom() {
int randomIndex = rand.nextInt(values.size());
return values.get(randomIndex);
}
}#include <vector>
#include <cstdlib>
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
class Solution {
std::vector<int> values;
public:
Solution(ListNode* head) {
ListNode* node = head;
while (node) {
values.push_back(node->val);
node = node->next;
}
}
int getRandom() {
int randomIndex = std::rand() % values.size();
return values[randomIndex];
}
};class ListNode {
constructor(val) {
this.val = val;
this.next = null;
}
}
class Solution {
constructor(head) {
this.values = [];
let node = head;
while (node !== null) {
this.values.push(node.val);
node = node.next;
}
}
getRandom() {
const randomIndex = Math.floor(Math.random() * this.values.length);
return this.values[randomIndex];
}
}typedef struct ListNode {
int val;
struct ListNode *next;
} ListNode;
typedef struct {
int *values;
int size;
} Solution;
Solution* solutionCreate(ListNode* head) {
Solution* obj = (Solution*) malloc(sizeof(Solution));
obj->size = 0;
ListNode* temp = head;
while (temp) {
obj->size++;
temp = temp->next;
}
obj->values = (int *)malloc(obj->size * sizeof(int));
temp = head;
int index = 0;
while (temp) {
obj->values[index++] = temp->val;
temp = temp->next;
}
return obj;
}
int solutionGetRandom(Solution* obj) {
int randomIndex = rand() % obj->size;
return obj->values[randomIndex];
}
void solutionFree(Solution* obj) {
free(obj->values);
free(obj);
}using System;
using System.Collections.Generic;
public class ListNode {
public int val;
public ListNode next;
public ListNode(int x) { val = x; }
}
public class Solution {
private List<int> values = new List<int>();
private Random rand = new Random();
public Solution(ListNode head) {
while (head != null) {
values.Add(head.val);
head = head.next;
}
}
public int GetRandom() {
int randomIndex = rand.Next(values.Count);
return values[randomIndex];
}
}In Python, this approach stores all the linked list values in a list during initialization. The getRandom function uses Python's random.choice() to return a value from the list, ensuring equal probability.
Time Complexity: O(N) for preprocessing, O(1) for getRandom.
Space Complexity: O(N) - for storing the list in a Python list.
Approach 2: Approach 2: Reservoir Sampling
Reservoir Sampling is an efficient algorithm that allows you to randomly select a single item from a stream (or a linked list) of unknown length with all items having an equal probability. You can accomplish this by traversing the linked list node by node, replacing the selected item with decreasing probability.
import random
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def __init__(self, head: ListNode):
self.head = head
def getRandom(self) -> int:
node, reservoir, count = self.head, None, 0
while node:
if random.randint(0, count) == 0:
reservoir = node.val
node = node.next
count += 1
return reservoirimport java.util.Random;
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
class Solution {
private ListNode head;
private Random rand;
public Solution(ListNode head) {
this.head = head;
this.rand = new Random();
}
public int getRandom() {
ListNode node = head;
int reservoir = node.val;
int count = 1;
while (node != null) {
if (rand.nextInt(count) == 0) {
reservoir = node.val;
}
count++;
node = node.next;
}
return reservoir;
}
}#include <cstdlib>
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
class Solution {
ListNode* head;
public:
Solution(ListNode* head) : head(head) {}
int getRandom() {
ListNode* node = head;
int reservoir = node->val;
int count = 1;
while (node) {
if (std::rand() % count == 0) {
reservoir = node->val;
}
count++;
node = node->next;
}
return reservoir;
}
};class ListNode {
constructor(val) {
this.val = val;
this.next = null;
}
}
class Solution {
constructor(head) {
this.head = head;
}
getRandom() {
let node = this.head;
let reservoir = node.val;
let count = 1;
while (node) {
if (Math.floor(Math.random() * count) === 0) {
reservoir = node.val;
}
count++;
node = node.next;
}
return reservoir;
}
}typedef struct ListNode {
int val;
struct ListNode *next;
} ListNode;
typedef struct {
ListNode *head;
} Solution;
Solution* solutionCreate(ListNode* head) {
Solution* obj = (Solution*) malloc(sizeof(Solution));
obj->head = head;
return obj;
}
int solutionGetRandom(Solution* obj) {
ListNode* node = obj->head;
int reservoir = node->val;
int count = 1;
while (node) {
if (rand() % count == 0) {
reservoir = node->val;
}
count++;
node = node->next;
}
return reservoir;
}
void solutionFree(Solution* obj) {
free(obj);
}using System;
public class ListNode {
public int val;
public ListNode next;
public ListNode(int x) { val = x; }
}
public class Solution {
private ListNode head;
private Random rand;
public Solution(ListNode head) {
this.head = head;
this.rand = new Random();
}
public int GetRandom() {
ListNode node = head;
int reservoir = node.val;
int count = 1;
while (node != null) {
if (rand.Next(count) == 0) {
reservoir = node.val;
}
node = node.next;
count++;
}
return reservoir;
}
}Utilizing Python's random number generator, this solution efficiently picks a random node from the linked list using reservoir sampling, where each item maintains equal likelihood of being selected throughout.
Time Complexity: O(N) for getRandom.
Space Complexity: O(1).
Approach 3: Default Approach
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
type Solution struct {
head *ListNode
}
func Constructor(head *ListNode) Solution {
return Solution{head}
}
func (this *Solution) GetRandom() int {
n, ans := 0, 0
for node := this.head; node != nil; node = node.Next {
n++
x := 1 + rand.Intn(n)
if n == x {
ans = node.Val
}
}
return ans
}
/**
* Your Solution object will be instantiated and called as such:
* obj := Constructor(head);
* param_1 := obj.GetRandom();
*/Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Preprocessing with Array | Time Complexity: O(N) for preprocessing, O(1) for |
| Approach 2: Reservoir Sampling | Time Complexity: O(N) for |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Preprocessing with Array | O(n) preprocessing, O(1) per getRandom() | O(n) | When memory is available and getRandom() will be called many times |
| Reservoir Sampling | O(n) per getRandom() | O(1) | When list size is unknown or memory is constrained |
Frequently asked questions
Is Linked List Random Node easy or hard?
Linked List Random Node is rated Medium difficulty on LeetCode. The traversal itself is simple, but recognizing and correctly implementing reservoir sampling requires understanding of probability and randomized algorithms.
How to solve Linked List Random Node in O(n)?
Use reservoir sampling while iterating through the linked list. Keep the current node as the answer with probability 1/i where i is the index of the node during traversal. After reaching the end, the stored value is guaranteed to be uniformly random across all nodes.
What is the best approach for Linked List Random Node?
Reservoir Sampling is the optimal interview approach. It scans the linked list once and selects each node with probability 1/n without storing the entire list. The algorithm runs in O(n) time per call and uses O(1) extra space.
Is Linked List Random Node asked at Google/Amazon/Meta?
This problem represents a classic reservoir sampling interview concept and has appeared in interviews at companies like Google, Amazon, and Meta. It tests understanding of probability, streaming algorithms, and linked list traversal.
What data structure is used in Linked List Random Node?
The core structure is a singly linked list. The optimized solution also relies on the reservoir sampling technique from randomized algorithms, while an alternative implementation stores node values in an array for constant-time random access.
What is the time complexity of Linked List Random Node?
The reservoir sampling solution runs in O(n) time for each getRandom() call because it traverses the linked list once. The preprocessing array approach requires O(n) time initially but answers each random query in O(1) time afterward.
Linked List Random Node Python or Java solution approach?
In Python or Java, iterate through the linked list while counting nodes and randomly replacing the current answer with probability 1/i. This implements reservoir sampling and guarantees uniform probability using only constant extra memory.