# 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
{
// IF list is empty
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

// Iterate from second element to nth element
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;
}
{
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

else //make the next of the current node point to the present head and make the current node as the new head
{
}

//O(1) constant time
}

{
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