Python LinkedList One and K Random Nodes Algorithm using Random Sampling


  • 0
    U
    # 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()
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.