Linked List Random Node

Problem Statement:-

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 head of the singly-linked list head.

• 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 chosen.

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

Problem Explanation with examples:-

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.

Example 2

Input
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1, 2]], [], [], [], [], []]
Output
[null, 2, 1, 2, 1, 2]
Explanation
Solution solution = new Solution([1, 2]);
solution.getRandom(); // return 2
solution.getRandom(); // return 1
solution.getRandom(); // return 2
solution.getRandom(); // return 1
solution.getRandom(); // return 2
// getRandom() should return either 1 or 2 randomly. Each element should have equal probability of returning.

Example 3

Input
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1]], [], [], [], [], []]
Output
[null, 1, 1, 1, 1, 1]
Explanation
Solution solution = new Solution([1]);
solution.getRandom(); // return 1
solution.getRandom(); // return 1
solution.getRandom(); // return 1
solution.getRandom(); // return 1
solution.getRandom(); // return 1
// getRandom() should return 1. Since there is only one element in the data structure, it is always returned.

Constraints

The number of nodes in the linked list will be in the range [1, 10^4].
-10^4 <= Node.val <= 10^4
At most 10^4 calls will be made to getRandom.

Intuition:-

• It's a simple object-oriented problem with a linked list,

• We just need to initialize the linked list and generate a random node and return its value,

• We can use the random module to generate a random number between 1 and the length of the linked list.

• As direct access to the linked list is not possible, we need to traverse the linked list to get the value of the random node generated and return it.

Solution:-

• We initialize the head of the linked list in the constructor.

• We initialize a variable n to store the length of the linked list.

• Traverse the linked list and increment n by 1 for each node.

• Next, assign the value of n to the count variable on the object.

• Next, we define the getRandom function in which we generate a random number between 1 and the length of the linked list.

• If the random number generated is 1, we return the value of the head of the linked list.

• Else, a y variable is initialized to 1 and a temp variable is initialized to the head of the linked list.

• We traverse the linked list and increment y by 1 for each node, until y is equal to the random number generated.

• Also, with each traversal iteration, we move the temp variable to the next node.

• Finally, we return the value of the temp node.

• Another solution could be to store all the values of the linked list in a list and then generate a random number between 0 and the length of the list and return the value at that index, but this would take O(n) space.

Code:-

JAVA Solution

class Solution {
    public Solution(ListNode head) {
        this.head = head;
        int n = 0;
        ListNode temp = this.head;
        while (temp != null) {
            n += 1;
            temp = temp.next;
        }
        this.count = n;
    }

    public int getRandom() {
        int x = (int) (Math.random() * this.count) + 1;
        if (x == 1) {
            return this.head.val;
        }
        int y = 1;
        ListNode temp = this.head;
        while (y != x) {
            temp = temp.next;
            y += 1;
        }
        return temp.val;
    }
}

Python Solution

class Solution:

    def __init__(self, head: Optional[ListNode]):
        self.head = head
        n = 0
        temp = self.head
        while temp:
            n += 1
            temp = temp.next

        self.count = n

    def getRandom(self) -> int:
        x = random.randint(1,self.count)
        if x == 1:
            return self.head.val

        y = 1
        temp = self.head
        while y != x:
            temp = temp.next
            y += 1

        return temp.val

Complexity Analysis:-

TIME:-

Time complexity is O(n), as we traverse the linked list to get the length of the linked list

SPACE:-

Space complexity is O(1), as we did not use any extra space.

References:-

• Random RandInt function

• Linked List

Connect with me:-

• Twitter

• Github

• LinkedIn