vendredi 7 janvier 2022

Linked List Random Node (Leetcode problem number 382)

https://leetcode.com/problems/linked-list-random-node/

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.

I am trying to find the solution for this problem. But for some reason it is only returning the 1st element of linked list. I even copied their solution given by LeetCode but still no result.

class Solution:
    def __init__(self, head):
        """
        @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node.
        """
        self.head = head

    def getRandom(self):
        """
        Returns a random node's value.
        """
        scope = 1
        chosen_value = 0
        curr = self.head

        while curr:
            # decide whether to include the element in reservoir
            if random.random() < 1 / scope:
                chosen_value = curr.val
            # move on to the next node
            curr = curr.next
            scope += 1
        return chosen_value
Refer below screenshot for more clarity
Output
[null,1,1,1,1,1]
Expected output
[null,3,3,2,2,3] #Numbers should be random

I am new to python so please help me.

Thanks in Advance

LeetCode Screenshot




Aucun commentaire:

Enregistrer un commentaire