Linked List Random Node - LeetCode
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. Implement the Solution class:
Solution(ListNode head) Initializes the object with the integer array nums. int getRandom() Chooses a node randomly from the list and returns its value. All the nodes of the list should be equally likely to be choosen.
Example 1:
Input [“Solution”, “getRandom”, “getRandom”, “getRandom”, “getRandom”, “getRandom”] [[[1, 2, 3]], [], [], [], [], []] Output [null, 1, 3, 2, 2, 3] Explanation Solution solution = new Solution([1, 2, 3]); solution.getRandom(); // return 1 solution.getRandom(); // return 3 solution.getRandom(); // return 2 solution.getRandom(); // return 2 solution.getRandom(); // return 3 // getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.
Constraints:
The number of nodes in the linked list will be in the range [1, 104].
-104 <= Node.val <= 104
At most 104 calls will be made to getRandom.
- code #reservoirSampling
class Solution:
def __init__(self, head: ListNode):
self.head = head
def getRandom(self) -> int:
scope = 1
chosen_value = 0
curr = self.head
while curr:
# decide whether to include the element in reservoir
if random.random() < 1 / scope:
chosen_value = curr.val
# move on to the next node
curr = curr.next
scope += 1
return chosen_value
- code
class Solution:
def __init__(self, head: ListNode):
self.range = []
while head:
self.range.append(head.val)
head = head.next
def getRandom(self) -> int:
pick = int(random.random() * len(self.range))
# pick = randint(0, len(self.range) - 1)
return self.range[pick]
- code
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def __init__(self, head: Optional[ListNode]):
self.h = head
self.length = 0
while head:
self.length += 1
head = head.next
def getRandom(self) -> int:
r = randint(0, self.length - 1)
h = self.h
while r > 0:
r -= 1
h = h.next
return h.val
# Your Solution object will be instantiated and called as such:
# obj = Solution(head)
# param_1 = obj.getRandom()