Last updated on October 6th, 2024 at 08:34 pm

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

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.

1. 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;
    }
};

2. 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;
    }
}

3. 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
};

4. 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