LeetCode-Solutions/Python/linked-list-random-node.py at master · pythonpeixun/LeetCode-Solutions · GitHub

31 lines (23 loc) · 766 Bytes

# Time: O(n)

# Space: O(1)

from random import randint

class Solution(object):

def __init__(self, head):

"""

@param head The linked list's head. Note that the head is guanranteed to be not null, so it contains at least one node.

:type head: ListNode

"""

self.__head = head

# Proof of Reservoir Sampling:

# https://discuss.leetcode.com/topic/53753/brief-explanation-for-reservoir-sampling

def getRandom(self):

"""

Returns a random node's value.

:rtype: int

"""

reservoir = -1

curr, n = self.__head, 0

while curr:

reservoir = curr.val if randint(1, n+1) == 1 else reservoir

curr, n = curr.next, n+1

return reservoir

Expand file tree