Leetcode 382 || Linked List Random Node

Problem link

https://leetcode.com/problems/linked-list-random-node/

Description

A linked list is given as input. There are two functions we need to implement. One of them is to initialize the LinkedList and another one is to get random values. And we have to return the value of a random node, not the node.

Solution

So we can first think of creating a new array with all the values of the given LinkedList. Then we can use a built-in random function to get values from the array. But if the LinkedList is a bit large, it will take more memory to save all values in an array. So Let's try to solve this without using any extra memory.

To get random values in the range(0 to length of the linked list), let's find out the length of the given LinkedList while initializing it.

Then inside the getRandom function, generate a random value first. Then return the value of the random node.

It's done. Isn't is simple?

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.head = head

        node = self.head
        self.length = 0
        # get the length of the given list while initializing
        while node:
            self.length += 1
            node = node.next

    def getRandom(self) -> int:
        # to return random node value, let's generate a random value first in the range of length of the linkedlist
        rand = random.randint(0,self.length-1)
        node = self.head
        # use loop to reach the random'th node
        while rand and node:
            if node.next == None:
                return node.val

            node = node.next
            rand -= 1
        return node.val

# Your Solution object will be instantiated and called as such:
# obj = Solution(head)
# param_1 = obj.getRandom()

Do you like this solution? Let me know if you have solved it in any other efficient way. Thanks for reading my article. Happy coding :D