algoadvance

Leetcode 382. Linked List Random Node

Problem Statement

Given a singly linked list, the task is to write a function that returns a random node’s value from the linked list. Each node must have the same probability of being chosen.

You need to 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.

Clarifying Questions

1. What is the structure of the ListNode?
   • The ListNode can be defined as:

     public class ListNode {
         int val;
         ListNode next;
         ListNode(int x) { val = x; }
     }
     

2. What is the length of the linked list?
   • The length of the linked list is not predefined, and it can be any length.
3. Can the linked list contain duplicate values?
   • Yes, it can contain duplicate values.
4. Can the linked list be null?
   • For the purpose of this problem, assume the list is non-empty.

Strategy

To ensure every node has the same probability of being chosen, we can implement a solution using Reservoir Sampling. Here’s the approach:

1. Initialization (Solution(ListNode head))
   • Store the reference of the head node.
2. Retrieve a random node (getRandom())
   • Traverse the linked list while maintaining a counter.
   • Use a random number generator to decide if the current node should replace the previously selected node.
   • Use the formula rand.nextInt(i + 1) where i is the index of the current node. This ensures each node has a 1/(i+1) chance of being chosen.

Code

import java.util.Random;

public class Solution {
    private ListNode head;
    private Random rand;

    /** @param head The linked list's head. */
    public Solution(ListNode head) {
        this.head = head;
        this.rand = new Random();
    }
    
    /** Returns a random node's value. */
    public int getRandom() {
        ListNode current = head;
        int result = current.val;
        int index = 1;

        while (current.next != null) {
            current = current.next;
            
            if (rand.nextInt(index + 1) == 0) {
                result = current.val;
            }
            
            index++;
        }
        
        return result;
    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

Time Complexity

• Initialization: O(1) - Storing the head reference and creating the Random object both take constant time.
• getRandom: O(N) - We traverse the entire linked list, so time complexity is proportional to the length of the linked list (N).

This solution ensures that each node in the linked list has an equal probability of being chosen by utilizing reservoir sampling.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?