Select a random node from a singly linked list

Given a singly linked list, select a random node from linked list (the probability of picking a node should be 1/N if there are N nodes in list). You are given a random number generator.

Method 1(Simple Solution)

In this method we need to traverse linked list two times

Algorithm

1. Count number of nodes by traversing the list.

2. Traverse the list again and select every node with probability 1/N.
     a. Generate a random number from 0 to N-i for i’th node, and selecting the i’th node     only if generated number is equal to 0 (or any other fixed number from 0 to N-i).

Method 2

In this method we will traverse linked list only one time by using Reservoir Sampling

Algorithm

1. Initialize result as the first node ie, result = head->data and make  n=2

2. Traverse the linked list from second node

    a. Generate a random number from 0 to n-1. Let it be rand.

    b. If rand is equal to zero(we could choose another number from 0 to n-1), then replace     result with current node.

    c. Increment value of n and move to the next node

Step 2 makes sure that the probability of picking a node should be 1/N

C++ Program

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

struct LLNode{
	int data;
	LLNode *next;	
};
// Function to create newNode in a linkedlist
LLNode* newNode(int data)
{
    LLNode *temp = new LLNode;
    temp->data = data;
    temp->next = NULL;
    return temp;
}
// A reservoir sampling based function to print a
// random node from a linked list
void randomNode(LLNode *head)
{
    // IF list is empty
    if (head == NULL)
       return;
 
    // Use a different seed value so that we don't get
    // same result each time we run this program
    srand(time(NULL));
 
    // Initialize result as first node
    int result = head->data;
 
    // Iterate from second element to nth element
    LLNode *current = head;
    int n;
    for (n=2; current!=NULL; n++)
    {
        // change result with probability 1/n
        if (rand() % n == 0)
           result = current->data;
 
        // Move to next node
        current = current->next;
    }
 
    cout<<"Randomly selected node is "<<result<<endl;
}
void insertAtBeginning(LLNode**head,int dataToBeInserted)
{
	LLNode*curr=new LLNode;
	//make a new node with this data and next pointing to NULL
	curr->data=dataToBeInserted;
	curr->next=NULL;

	if(*head==NULL) //if list is empty then set the current formed node as head of list
			*head=curr;
		
	else //make the next of the current node point to the present head and make the current node as the new head
		{
			curr->next=*head;
			*head=curr;
		}
		
		//O(1) constant time
}


void display(LLNode**head)
{
	LLNode*temp=*head;
	while(temp!=NULL) //till the list ends (NULL marks ending of list)
		{
			if(temp->next!=NULL)
			cout<<temp->data<<" ->";
			else
			cout<<temp->data;
			
			temp=temp->next; //move to next node
		}
		//O(number of nodes)
	cout<<endl;
}

int main() 
{    
	
	LLNode *head = NULL; //initial list has no elements

	insertAtBeginning(&head,5);
	insertAtBeginning(&head,4);
	insertAtBeginning(&head,3);
	insertAtBeginning(&head,2);
	insertAtBeginning(&head,1);
	
	cout<<"\nCurrent List is :-\n";
	display(&head);
	randomNode(head);
	return 0;
}
Try It

 


Next > < Prev
Scroll to Top