-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy path382.py
More file actions
47 lines (38 loc) · 1.15 KB
/
382.py
File metadata and controls
47 lines (38 loc) · 1.15 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
# Author: btjanaka (Bryon Tjanaka)
# Problem: (LeetCode) 382
# Title: Linked List Random Node
# Link: https://leetcode.com/problems/linked-list-random-node/
# Idea: See Reservoir Sampling on Wikipedia: https://en.wikipedia.org/wiki/Reservoir_sampling
# Difficulty: medium
# Tags: linked-list, random
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
from random import randint
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.
"""
itr = self.head_
val = itr.val
i = 2
itr = itr.next
while itr != None:
j = randint(1, i)
if j == 1:
val = itr.val
i += 1
itr = itr.next
return val
# Your Solution object will be instantiated and called as such:
# obj = Solution(head)
# param_1 = obj.getRandom()