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
Aucun commentaire:
Enregistrer un commentaire