Last updated on February 12th, 2025 at 01:51 am
Here, we see a Linked List Random Node LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Reservoir-Sampling
Companies
Level of Question
Medium
Linked List Random Node LeetCode Solution
Table of Contents
1. 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.
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.
2. Coding Pattern Used in Solution
The coding pattern used in the provided code is “Reservoir Sampling”. This is a probabilistic algorithm used to randomly select a single element from a stream or linked list of unknown size, ensuring that each element has an equal probability of being chosen.
3. Code Implementation in Different Languages
3.1 Linked List Random Node C++
class Solution {
private:
ListNode* head;
public:
Solution(ListNode* head) {
this->head = head;
std::srand(std::time(0));
}
int getRandom() {
int count = 0;
int result = 0;
ListNode* curr = head;
while (curr) {
count++;
if (std::rand() % count == 0) {
result = curr->val;
}
curr = curr->next;
}
return result;
}
};
3.2 Linked List Random Node Java
class Solution {
int N = 0;
ListNode head = null;
public Solution(ListNode head) {
this.head = head;
}
public int getRandom() {
ListNode p = this.head;
int i = 1, ans = 0;
while (p != null) {
if (Math.random() * i < 1) ans = p.val;
p = p.next;
i ++;
}
return ans;
}
}
3.3 Linked List Random Node JavaScript
var Solution = function(head) {
this.res = [];
let curr = head;
while(curr !== null) {
this.res.push(curr)
curr = curr.next;
}
this.length = this.res.length;
};
Solution.prototype.getRandom = function() {
return this.res[Math.floor(Math.random() * this.length)].val
};
3.4 Linked List Random Node Python
class Solution(object):
def __init__(self, head):
self.head = head
def getRandom(self):
count = 0
result = None
curr = self.head
while curr:
count += 1
if random.randint(1, count) == 1:
result = curr.val
curr = curr.next
return result
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n) | O(1) |
| Java | O(n) | O(1) |
| JavaScript | O(n) | O(1) |
| Python | O(n) | O(n) |
- The C++, Java, and Python implementations are more memory-efficient and suitable for large linked lists.
- The JavaScript implementation is easier to understand but uses more memory due to the array storage.
- All implementations ensure uniform random selection of a node’s value.