题目
Given a singly linked list, return a random node’s value from the linked list. Each node must have the same probability of being chosen.
Follow up: What if the linked list is extremely large and its length is unknown to you? Could you solve this efficiently without using extra space?
解题思路
代码
class Solution:
def __init__(self, head: ListNode):
"""
@param head The linked list's head.
Note that the head is guaranteed to be not null, so it contains at least one node.
"""
self.head = head
def getRandom(self) -> int:
"""
Returns a random node's value.
"""
count = res = 0
cur = self.head
while cur:
count += 1
if random.random() <= 1 / count:
res = cur.val
cur = cur.next
return res
