Linked List Random Node LeetCode Solution

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

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 SolutionC++

``````class Solution {
private:
public:
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 SolutionJava

``````class Solution {
int N = 0;
ListNode head = null;
public Solution(ListNode 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 SolutionJavaScript

``````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):