Here, We see Linked List Random Node LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.
List of all LeetCode Solution
Linked List Random Node LeetCode Solution
Table of Contents
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.
Linked List Random Node LeetCode Solution 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;
}
};
Code language: PHP (php)
Linked List Random Node Solution 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;
}
}
Code language: JavaScript (javascript)
Linked List Random Node Solution 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
};
Code language: JavaScript (javascript)
Linked List Random Node Solution 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