simple Python solution


  • 0

    Just connect the tail to the head to form a circle. Then run random steps to get a random value.

    class Solution(object):
        def __init__(self, head):
            self.l = 0
            self.h = head
            while self.h.next:
                self.h = self.h.next
                self.l += 1
            self.h.next = head
            self.l += 1
    
        def getRandom(self):
            import random
            N = random.randint(0, self.l-1)
            for i in xrange(N):
                self.h = self.h.next
            return self.h.val
    

Log in to reply
 

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