Linked List Random Node Solution in C++

Explore More Solutions

Problem Description

Welcome to the world of linked lists, where every node is a little island, and they’re all connected by the magical threads of pointers! The problem at hand is to create a class that can return a random node’s value from a linked list. Sounds simple, right? Well, it’s like trying to pick a random candy from a jar without looking, but the jar is a bit too deep, and you can’t just reach in and grab one.

Imagine you’re at a party, and you want to randomly select someone to tell a joke. You could just point at someone, but what if they’re the shy type? You need a method that ensures everyone has an equal chance of being chosen, just like our linked list nodes!

Code Solution


class Solution {
 public:
  /** @param head The linked list's head.
      Note that the head is guaranteed to be not null, so it contains at least
     one node. */
  Solution(ListNode* head) : head(head) {}

  /** Returns a random node's value. */
  int getRandom() {
    int res = -1;
    int i = 1;

    for (ListNode* curr = head; curr; curr = curr->next, ++i)
      if (rand() % i == 0)
        res = curr->val;

    return res;
  }

 private:
  ListNode* head;
};

Approach

The approach here is a classic example of the Reservoir Sampling technique. As we traverse the linked list, we maintain a counter to keep track of the current node’s index. For each node, we generate a random number and decide whether to keep its value based on the probability of 1/i, where i is the index of the current node. This ensures that every node has an equal chance of being selected, making it a fair game!

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n)
Space Complexity	O(1)

Real-World Example

Think of a reality show where contestants are eliminated one by one. At the end of each episode, the host randomly selects a contestant to save from elimination. The host can’t just pick their favorite; they need to ensure that every contestant has an equal chance of being saved. This is exactly what our code does with the linked list nodes!