Select a Random Node from a Linked List

Introduction 

Data Structures and Algorithms are a very prominent part of tech interviews to test the candidate’s problem-solving ability. To test this aspect, interviewers usually present the candidate with a programming question. 

In this blog, we will discuss one such question. 

Recommended Topic, Floyds Algorithm

Problem Statement

You are given a Linked List, a Singly Linked List specifically. You are supposed to return a random node value from the Linked List. Each node should have an equal possibility of getting selected. 

Explanation of the Problem Statement 

So, basically, you are given a Singly Linked List. You are to write a function that returns a random node value from the Linked List every time it is called.  

But, the catch here is that, let’s say there are ‘n’ nodes in the Linked List. Then, the probability of every node getting selected should be 1/n. You should keep in mind to maintain this. 

You cannot return as you feel like. You should think of such a mechanism that actually makes it random.  

Sample Example 

Consider a Linked List(Singly Linked List) with 4 nodes. This means that its length is 4. Something like this: 

If the above-Linked List is considered, then on call of the function, let’s say random_node(). Every time, it should return a different node value, like 3 on the first call, 1 on the second call, and so on. 

Approach - 1: Brute Force Approach

So, there is the use of the word random in the question itself, which leads to a hint on using some function or way of generating some random value. 

Also, you may have observed till now that it is about being random implicitly through some mechanism.  

For that, let’s assign index value for understanding sake to the nodes of the singly Linked List. 

So, let us say we know the length and therefore, we have indexed it accordingly. Now, we generate a random value in [0,length_of_linked_list). 

Now, whatever value we get we return that specific node value. 

For example: If the random value produced is 3, then 4 is returned. 

Now, there are two sub-tasks- finding the length of the Linked List and generating a random value less than the length of the Linked List.   
The length can be found using a loop till the next node is not null. 

For random value, every language has some function that produces random value. So that can be employed for this. Then, to reduce that value to be less than the length of the Linked List, the modulus can be taken with the length of the Linked List. 

Steps of the Algorithm

1. Find the length of the Linked List. To do so, initialize a variable to 0 and traverse the Linked List till the end of it and increment the variable every time a node is encountered. 
2. Generate a random value using the rand() function(in C++) and make it less than the length of the Linked List, let us say this is stored in rand_val.
3. Now, traverse the Linked List till you cover the number of nodes equal to the rand_val. 
4. Return the value of this node. 

Implementation in C++

Code for the above-explained approach in C++ is as follows: 

#include<bits/stdc++.h>
using namespace std;

class Node    //Nodes of the Linked List
{
    public:
        int value;
        Node* next;
        Node(int num)
        {
          this->value=num;
          this->next=NULL;
        }
}; 

class linked_list   //Linked List
{
   Node *head;  
   int length=0;
   public: 
    linked_list()
    {
        head=NULL; 
    }
    void insert(int num);
    void find_length();
    void rand_value();  
}; 

void linked_list::insert(int num)   //insert nodes in Linked List
{
    Node* newNode=new Node(num);
     
    if(head==NULL)
    {
        head=newNode;
        return;
    }
  
    Node* t=head;
    while(t->next!=NULL) 
    {
        t=t->next;
    }
    t->next=newNode;
} 

void linked_list::find_length()   //finding length of he Linked List
{
    Node* t=head;
    while(t!=NULL) 
    {
        t=t->next; 
        length++;
    }
} 

void linked_list::rand_value()    //producing random node value
{
    if(length==0)
        return;
    
    time_t current_time;
    srand(time(&current_time)); 
    int rand_val=(rand()%length);
    int result=head->value;    
    Node* t=head;
    for(int i=0;i<rand_val;i++)  
    {                             
        t=t->next;
    }
    cout<<"Random value is: "<<t->value<<"\n";
}

int main()
{
	cout<<"First make a Linked List\n";  
	return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Input:

linked_list l;
l.insert(1);
l.insert(2);
l.insert(3);
l.insert(4); 
l.insert(5);
l.find_length();
l.rand_value(); 

Output:

First make a Linked List
Random value is: 2    //Time is 23:20 25/5/2022 


First make a Linked List
Random value is: 1    //Time is 23:21 25/5/2022 

Complexity Analysis

Time Complexity: O(n) 

So, we see that we traverse the whole Linked List once for length and once for the random value of the node. Therefore, the Time Complexity is O(n+n) or O(n). Here, ‘n’ is the number of nodes in the Linked List. 

  
Space Complexity: O(n) 

Space complexity is also linear as the memory required increases linearly with the addition of each node. But, one thing to note here is that we traverse the Linked List twice. 
Of course, you can make small changes to run the code for the required number of test cases.