Linked list random node
September 6, 2022
linked-listProblem URL: Linked list random node
When we initialize the solution class, we will traverse the whole list and store it's values to a list. Then each time we are asked to get a random number, we will use random module to choose a value from the list and return.
# 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.values = self._getValues(head)
def getRandom(self) -> int:
return random.choice(self.values)
def _getValues(self, head: Optional[ListNode]) -> List[int]:
values = []
pointer = head
while pointer:
values.append(pointer.val)
pointer = pointer.next
return values
# Your Solution object will be instantiated and called as such:
# obj = Solution(head)
# param_1 = obj.getRandom()
Time Complexity: O(n)
for init, O(1)
for getRandom
Space Complexity: O(n)