Created
December 2, 2020 09:57
-
-
Save kuntalchandra/9d15263b2277c3392327b618c7cec56f to your computer and use it in GitHub Desktop.
Linked List Random Node
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
""" | |
Linked List Random Node | |
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? | |
Example: | |
// Init a singly linked list [1,2,3]. | |
ListNode head = new ListNode(1); | |
head.next = new ListNode(2); | |
head.next.next = new ListNode(3); | |
Solution solution = new Solution(head); | |
// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning. | |
solution.getRandom(); | |
""" | |
from random import random | |
# 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: 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.numbers = [] | |
self.get_range(head) | |
def get_range(self, head: ListNode): | |
while head: | |
self.numbers.append(head.val) | |
head = head.next | |
def getRandom(self) -> int: | |
""" | |
Returns a random node's value. | |
""" | |
idx = int(random() * len(self.numbers)) | |
return self.numbers[idx] | |
# Your Solution object will be instantiated and called as such: | |
# obj = Solution(head) | |
# param_1 = obj.getRandom() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment