# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None from random import randint, random class Solution(object): 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. :type head: ListNode """ self.head=head def getRandom(self): """ Returns a random node's value. :rtype: int """ head = self.head num = 1 while head: if random() * num <= 1: random_val = head.val num += 1 head = head.next return random_val def getRandomForK(self, k=1): """ Returns a random node's value. :rtype: int """ head = self.head ans =  index = 0 while index < k: ans.append(head.val) index += 1 num = k + 1 while head: random_number = randint(1, num) if random_number <= k: ans[random_number - 1] = head.val num += 1 head = head.next return ans # Your Solution object will be instantiated and called as such: # obj = Solution(head) # param_1 = obj.getRandom()
Python LinkedList One and K Random Nodes Algorithm using Random Sampling
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.