5 lines in Python


  • 1
    import random
    
    class Solution(object):
    
        def __init__(self, head):
            self.vals = []
            while head:
                self.vals += head.val,
                head = head.next
            
    
        def getRandom(self):
            return self.vals[random.randint(0, len(self.vals)-1)]
    

    This is the version that uses O(1) space but each sampling takes Theta(n) time. 4 lines.

    import random
    
    class Solution(object):
    
        def __init__(self, head):
            self.head = head
            
    
        def getRandom(self):
            cur, res, n = self.head.next, self.head.val, 1
            while cur:
                res, cur, n = cur.val if random.randint(1, n + 1) == 1 else res,\
                              cur.next,\
                              n + 1
            return res
    

Log in to reply
 

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