Welcome to Subscribe On Youtube

382. Linked List Random Node

Description

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.

 

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.

 

Constraints:

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

 

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?

Solutions

The challenge is to implement the solution in a way that each node has an equal probability of being chosen, given that the size of the linked list is unknown or may not fit into memory (thus, not allowing for a simple array-based solution where one could just pick a random index).

Reservoir Sampling

This solution uses a technique called Reservoir Sampling. It’s a fantastic strategy for sampling from a population of unknown size with uniform distribution. The idea is to iterate through each element (or node, in this case), deciding whether to keep it as the current answer or not, until you’ve seen all elements.

Why Reservoir Sampling Works for Large or Unknown Length Lists:

  1. Unknown Length: The beauty of Reservoir Sampling is that it doesn’t require knowledge of the population size (or the linked list’s length) beforehand. It processes each item (or node) one at a time and decides whether to include it in the sample (in this case, select it as the current answer).

  2. Efficiency: The algorithm only needs a single pass through the data, making it efficient for streaming data or large datasets where multiple passes are impractical or impossible.

  3. No Extra Space: Aside from variables for counting (n) and storing the current answer (ans), no additional storage is required. This is particularly advantageous when dealing with large data sets where storing all elements in memory would be infeasible.

Here’s a breakdown of how the code works:

  1. Initialization: The constructor simply stores the head of the list for future access.

  2. getRandom Function:

    • n is a counter for the nodes seen so far.
    • ans will store the value of the randomly selected node.
    • The loop iterates over each node in the list one by one.
    • For each node, it increments n (the count of nodes encountered so far).
    • x is assigned a random integer between 1 and n. This random number decides if the current node’s value should replace the previous ans value.
    • If x is equal to n, then ans is updated to the current node’s value. The probability of this happening is 1/n, ensuring that each node has an equal chance of being chosen. For example, when you’re at the first node, n is 1, so the probability of choosing that node is 100%. When you’re at the second node, there’s a 50% chance it becomes the answer, and so on.
    • Finally, after traversing all nodes, ans holds the value of a randomly selected node, which is returned.

Why It Works

The key part of this algorithm is the probability calculation that ensures each node has an equal chance of being selected. When you’re at the ith node, the probability that it gets chosen is 1/i. For it to be the final answer, it must also not be replaced by subsequent nodes. For the ith node and the next node, the probability that the ith node stays as the answer is (1/i) * (1 - 1/(i+1)) = 1/(i+1), and this logic extends to all nodes in the list.

Complexity

  • Time Complexity: O(N), where N is the number of nodes in the list, since it iterates through each node once.
  • Space Complexity: O(1), as it uses only a few variables for any size of input linked list.
  • /**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    private ListNode head;
    private Random random = new Random();

    public Solution(ListNode head) {
        this.head = head;
    }

    public int getRandom() {
        int ans = 0, n = 0;
        for (ListNode node = head; node != null; node = node.next) {
            ++n;
            int x = 1 + random.nextInt(n);
            if (n == x) {
                ans = node.val;
            }
        }
        return ans;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(head);
 * int param_1 = obj.getRandom();
 */

  • /**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* head;

    Solution(ListNode* head) {
        this->head = head;
    }

    int getRandom() {
        int n = 0, ans = 0;
        for (ListNode* node = head; node != nullptr; node = node->next) {
            n += 1;
            int x = 1 + rand() % n;
            if (n == x) ans = node->val;
        }
        return ans;
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(head);
 * int param_1 = obj->getRandom();
 */

  • # 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

    def getRandom(self) -> int:
        n = ans = 0
        head = self.head
        while head:
            n += 1
            x = random.randint(1, n)
            if n == x:
                ans = head.val
            head = head.next
        return ans


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

############

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
import random


class Solution(object):

  def __init__(self, head):
    """
    @param head The linked list's head.
    Note that the head is guaranteed to be not null, so it contains at least one node.
    :type head: ListNode
    """
    self.head = head

  def getRandom(self):
    """
    Returns a random node's value.
    :rtype: int
    """
    ans = self.head.val
    head = self.head
    idx = 1
    while head:
      if random.randrange(1, idx + 1) == idx:
        ans = head.val
      head = head.next
      idx += 1
    return ans

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



  • /**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
type Solution struct {
	head *ListNode
}

func Constructor(head *ListNode) Solution {
	return Solution{head}
}

func (this *Solution) GetRandom() int {
	n, ans := 0, 0
	for node := this.head; node != nil; node = node.Next {
		n++
		x := 1 + rand.Intn(n)
		if n == x {
			ans = node.Val
		}
	}
	return ans
}

/**
 * Your Solution object will be instantiated and called as such:
 * obj := Constructor(head);
 * param_1 := obj.GetRandom();
 */

All Problems

All Solutions