Select a Random Node from a Singly Linked List - GeeksforGeeks
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.
Below is a Simple Solution
1) Count number of nodes by traversing the list.
2) Traverse the list again and select every node with probability 1/N. The selection can be done by generating a random number from 0 to N-i for i'th node, and selecting the i'th node node only if generated number is equal to 0 (or any other fixed number from 0 to N-i).
Read full article from Select a Random Node from a Singly Linked List - GeeksforGeeks
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.
Below is a Simple Solution
1) Count number of nodes by traversing the list.
2) Traverse the list again and select every node with probability 1/N. The selection can be done by generating a random number from 0 to N-i for i'th node, and selecting the i'th node node only if generated number is equal to 0 (or any other fixed number from 0 to N-i).
The probability that the second last node is result = [Probability that the second last node replaces result] X [Probability that the last node doesn't replace the result] = [1 / (N-1)] * [(N-1)/N] = 1/NReservoir Sampling
(1) Initialize result as first node result = head->key (2) Initialize n = 2 (3) Now one by one consider all nodes from 2nd node onward. (3.a) Generate a random number from 0 to n-1. Let the generated random number is j. (3.b) If j is equal to 0 (we could choose other fixed number between 0 to n-1), then replace result with current node. (3.c) n = n+1 (3.d) current = current->next
How does this work? Let there be total N nodes in list. It is easier to understand from last node.The probability that last node is result simply 1/N [For last or N’th node, we generate a random number between 0 to N-1 and make last node as result if the generated number is 0 (or any other fixed number]The probability that second last node is result should also be 1/N.The probability that the second last node is result = [Probability that the second last node replaces result] X [Probability that the last node doesn't replace the result] = [1 / (N-1)] * [(N-1)/N] = 1/NSimilarly we can show probability for 3rd last node and other nodes.void
printRandom(
struct
node *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->key;
// Iterate from the (k+1)th element to nth element
struct
node *current = head;
int
n;
for
(n=2; current!=NULL; n++)
{
// change result with probability 1/n
if
(
rand
() % n == 0)
result = current->key;
// Move to next node
current = current->next;
}
printf
(
"Randomly selected key is %d\n"
, result);
}