Select a Random Node from a Singly Linked List

Read

Discuss(30+)

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

Count the number of nodes by traversing the list.
Traverse the list again and select every node with a probability of 1/N. The selection can be done by generating a random number from 0 to N-i for the node, and selecting the i’th node only if the generated number is equal to 0 (or any other fixed number from 0 to N-i).

We get uniform probabilities with the above schemes.

i = 1, probability of selecting first node = 1/N
i = 2, probability of selecting second node =
                   [probability that first node is not selected] * 
                   [probability that second node is selected]
                  = ((N-1)/N)* 1/(N-1)
                  = 1/N

Similarly, the probability of other selecting other nodes is 1/N
The above solution requires two traversals of the linked list.

How to select a random node with only one traversal allowed?
The idea is to use Reservoir Sampling. Following are the steps. This is a simpler version of Reservoir Sampling as we need to select only one key instead of the k keys.

(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

Below is the implementation of the above algorithm.

C++

/* C++ program to randomly select a node from a singly
linked list */
#include<stdio.h>
#include<stdlib.h>
#include <time.h>
#include<iostream>
using namespace std;
 
/* Link list node */
class Node
{
    public:
    int key;
    Node* next;
    void printRandom(Node*);
    void push(Node**, int);
     
};
 
// A reservoir sampling based function to print a
// random node from a linked list
void Node::printRandom(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
    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;
    }
 
    cout<<"Randomly selected key is \n"<< result;
}
 
/* BELOW FUNCTIONS ARE JUST UTILITY TO TEST */
 
/* A utility function to create a new node */
Node* newNode(int new_key)
{
    // allocate node 
    Node* new_node = (Node*) malloc(sizeof( Node));
 
    /// put in the key 
    new_node->key = new_key;
    new_node->next = NULL;
 
    return new_node;
}
 
/* A utility function to insert a node at the beginning
of linked list */
void Node:: push(Node** head_ref, int new_key)
{
    /* allocate node */
    Node* new_node = new Node;
 
    /* put in the key */
    new_node->key = new_key;
 
    /* link the old list of the new node */
    new_node->next = (*head_ref);
 
    /* move the head to point to the new node */
    (*head_ref) = new_node;
}
 
// Driver program to test above functions
int main()
{
    Node n1;
    Node *head = NULL;
    n1.push(&head, 5);
    n1.push(&head, 20);
    n1.push(&head, 4);
    n1.push(&head, 3);
    n1.push(&head, 30);
 
    n1.printRandom(head);
 
    return 0;
}
 
// This code is contributed by SoumikMondal

C

/* C program to randomly select a node from a singly
   linked list */
#include<stdio.h>
#include<stdlib.h>
#include <time.h>
 
/* Link list node */
struct Node
{
    int key;
    struct Node* next;
};
 
// A reservoir sampling based function to print a
// random node from a linked list
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);
}
 
/* BELOW FUNCTIONS ARE JUST UTILITY TO TEST  */
 
/* A utility function to create a new node */
struct Node *newNode(int new_key)
{
    /* allocate node */
    struct Node* new_node =
        (struct Node*) malloc(sizeof(struct Node));
 
    /* put in the key  */
    new_node->key  = new_key;
    new_node->next =  NULL;
 
    return new_node;
}
 
 
/* A utility function to insert a node at the beginning
  of linked list */
void push(struct Node** head_ref, int new_key)
{
    /* allocate node */
    struct Node* new_node = new Node;
 
    /* put in the key  */
    new_node->key  = new_key;
 
    /* link the old list of the new node */
    new_node->next = (*head_ref);
 
    /* move the head to point to the new node */
    (*head_ref)    = new_node;
}
 
 
// Driver program to test above functions
int main()
{
    struct Node *head = NULL;
    push(&head, 5);
    push(&head, 20);
    push(&head, 4);
    push(&head, 3);
    push(&head, 30);
 
    printRandom(head);
 
    return 0;
}

Java

// Java program to select a random node from singly linked list
 
import java.util.*;
 
// Linked List Class
class LinkedList {
 
    static Node head;  // head of list
 
    /* Node Class */
    static class Node {
 
        int data;
        Node next;
 
        // Constructor to create a new node
        Node(int d) {
            data = d;
            next = null;
        }
    }
 
    // A reservoir sampling based function to print a
    // random node from a linked list
    void printrandom(Node node) {
 
        // If list is empty
        if (node == null) {
            return;
        }
 
        // Use a different seed value so that we don't get
        // same result each time we run this program
        Math.abs(UUID.randomUUID().getMostSignificantBits());
 
        // Initialize result as first node
        int result = node.data;
 
        // Iterate from the (k+1)th element to nth element
        Node current = node;
        int n;
        for (n = 2; current != null; n++) {
 
            // change result with probability 1/n
            if (Math.random() % n == 0) {
                result = current.data;
            }
 
            // Move to next node
            current = current.next;
        }
 
        System.out.println("Randomly selected key is " + result);
    }
 
    // Driver program to test above functions
    public static void main(String[] args) {
 
        LinkedList list = new LinkedList();
        list.head = new Node(5);
        list.head.next = new Node(20);
        list.head.next.next = new Node(4);
        list.head.next.next.next = new Node(3);
        list.head.next.next.next.next = new Node(30);
 
        list.printrandom(head);
 
    }
}
 
// This code has been contributed by Mayank Jaiswal

Python3

# Python program to randomly select a node from singly
# linked list 
 
import random
 
# Node class 
class Node:
 
    # Constructor to initialize the node object
    def __init__(self, data):
        self.data= data
        self.next = None
 
class LinkedList:
 
    # Function to initialize head
    def __init__(self):
        self.head = None
 
    # A reservoir sampling based function to print a
    # random node from a linked list
    def printRandom(self):
 
        # If list is empty 
        if self.head is None:
            return
        if self.head and not self.head.next:
           print("Randomly selected key is %d" %(self.head.data))
 
        # Use a different seed value so that we don't get 
        # same result each time we run this program
        random.seed()
 
        # Initialize result as first node
        result = self.head.data
 
        # Iterate from the (k+1)th element nth element
        # because we iterate from (k+1)th element, or 
        # the first node will be picked more easily 
        current = self.head.next
        n = 2
        while(current is not None):
             
            # change result with probability 1/n
            if (random.randrange(n) == 0 ):
                result = current.data 
 
            # Move to next node
            current = current.next
            n += 1
 
        print("Randomly selected key is %d" %(result))
         
    # Function to insert a new node at the beginning
    def push(self, new_data):
        new_node = Node(new_data)
        new_node.next = self.head
        self.head = new_node
 
    # Utility function to print the LinkedList
    def printList(self):
        temp = self.head
        while(temp):
            print(temp.data,end=" ")
            temp = temp.next
 
 
# Driver program to test above function
llist = LinkedList()
llist.push(5)
llist.push(20)
llist.push(4)
llist.push(3)
llist.push(30)
llist.printRandom()
 
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)

C#

// C# program to select a random node 
// from singly linked list
using System;
     
// Linked List Class
public class LinkedList 
{
    Node head; // head of list
 
    /* Node Class */
    public class Node
    {
        public int data;
        public Node next;
 
        // Constructor to create a new node
        public Node(int d) 
        {
            data = d;
            next = null;
        }
    }
 
    // A reservoir sampling based function to print a
    // random node from a linked list
    void printrandom(Node node) 
    {
 
        // If list is empty
        if (node == null) 
        {
            return;
        }
 
        // Use a different seed value so that we don't get
        // same result each time we run this program
        //Math.abs(UUID.randomUUID().getMostSignificantBits());
 
        // Initialize result as first node
        int result = node.data;
 
        // Iterate from the (k+1)th element to nth element
        Node current = node;
        int n;
        for (n = 2; current != null; n++) 
        {
 
            // change result with probability 1/n
            if (new Random().Next() % n == 0) 
            {
                result = current.data;
            }
 
            // Move to next node
            current = current.next;
        }
 
        Console.WriteLine("Randomly selected key is " + 
                                               result);
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
        LinkedList list = new LinkedList();
        list.head = new Node(5);
        list.head.next = new Node(20);
        list.head.next.next = new Node(4);
        list.head.next.next.next = new Node(3);
        list.head.next.next.next.next = new Node(30);
 
        list.printrandom(list.head);
    }
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// Javascript program to select a random node 
// from singly linked list
 
 /* Node Class */
class Node
{
    constructor(d)
    {
        this.data=d;
        this.next = null;
    }
}
 
 // A reservoir sampling based function to print a
    // random node from a linked list
function printrandom(node)
{
    // If list is empty
        if (node == null) {
            return;
        }
   
        // Use a different seed value so that we don't get
        // same result each time we run this program
        //Math.abs(UUID.randomUUID().getMostSignificantBits());
   
        // Initialize result as first node
        let result = node.data;
   
        // Iterate from the (k+1)th element to nth element
        let current = node;
        let n;
        for (n = 2; current != null; n++) {
   
            // change result with probability 1/n
            if (Math.floor(Math.random()*n) == 0) {
                result = current.data;
            }
   
            // Move to next node
            current = current.next;
        }
   
        document.write("Randomly selected key is <br>" +
        result+"<br>");
}
 
// Driver program to test above functions
head = new Node(5);
head.next = new Node(20);
head.next.next = new Node(4);
head.next.next.next = new Node(3);
head.next.next.next.next = new Node(30);
 
printrandom(head);
 
// This code is contributed by rag2127
 
</script>

Output

Randomly selected key is 
4

Time Complexity: O(n), as we are using a loop to traverse n times. Where n is the number of nodes in the linked list.
Auxiliary Space: O(1), as we are not using any extra space.

Note that the above program is based on the outcome of a random function and may produce different outputs.

How does this work?
Let there be total N nodes in the list. It is easier to understand from the last node.
The probability that the last node is result simply 1/N [For the last or N’th node, we generate a random number between 0 to N-1 and make the last node as the result if the generated number is 0 (or any other fixed number]
The probability that the second last node is the 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/N

Similarly, we can show the probability for 3^rd last node and other nodes.

Another approach Using rand() Function:

Here in this Approach, we convert linked list to vector by storing every node value and than we apply rand() function on them and return the random node value.

Approach/Intuition:

here given linked list :

5 -> 20 -> 4 -> 3 -> 30.

we traverse over linked list and convert it into vector.

vector<int>v{5,20,4,3,30};

than we use rand() function.

int n=v.size() //size of the vector.

int RandomIndex=rand() % n;

and at the end we will return random node value from singly linked list.

Below is the code to implement the above approach:

C++

/* C++ program to randomly select a node from a singly
linked list */
 
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
 
/* Link list node */
class Node {
public:
    int key;
    Node* next;
    void printRandom(Node*);
    void push(Node**, int);
};
 
Node* newNode(int new_key)
{
    // allocate node
    Node* new_node = (Node*)malloc(sizeof(Node));
 
    /// put in the key
    new_node->key = new_key;
    new_node->next = NULL;
 
    return new_node;
}
 
/* A utility function to insert a node at the beginning
of linked list */
void Node::push(Node** head_ref, int new_key)
{
    /* allocate node */
    Node* new_node = new Node;
 
    /* put in the key */
    new_node->key = new_key;
 
    /* link the old list of the new node */
    new_node->next = (*head_ref);
 
    /* move the head to point to the new node */
    (*head_ref) = new_node;
}
 
void printRandom(Node* head)
{
    Node* temp = head;
    vector<int> v;
    while (temp != NULL) {
        v.push_back(temp->key);
        temp = temp->next;
    }
    int n = v.size();
    int randIndex = rand() % n;
    cout << v[randIndex] << endl;
}
 
// Driver's code
int main()
{
    Node n1;
    Node* head = NULL;
    n1.push(&head, 5);
    n1.push(&head, 20);
    n1.push(&head, 4);
    n1.push(&head, 3);
    n1.push(&head, 30);
    // function call
    printRandom(head);
    // code & approach contributed by Sanket Gode.
    return 0;
}

Java

/*package whatever //do not write package name here */
import java.io.*;
import java.util.*;
// Node of Linkedlist
class Node {
    int key;
    Node next;
    Node(int key)
    {
        this.key = key;
        this.next = null;
    }
}
class GFG {
    // Function to Print Random Values
    public static void printRandom(Node head)
    {
        Node temp = head;
        ArrayList<Integer> list = new ArrayList<Integer>();
        while (temp != null) {
            list.add(temp.key);
            temp = temp.next;
        }
        int n = list.size();
        Random rand = new Random();
        int randIndex = rand.nextInt(n);
        System.out.println(list.get(randIndex));
    }
    // Drivers Code
    public static void main(String[] args)
    {
        // Making List
        Node head = new Node(30);
        head.next = new Node(3);
        head.next.next = new Node(4);
        head.next.next.next = new Node(20);
        head.next.next.next.next = new Node(5);
        // Calling Function
        printRandom(head);
        // This Code is Contributed By Vikas Bishnoi
    }
}

Python3

import random
 
# Link list node
class Node:
    def __init__(self):
        self.key = 0
        self.next = None
 
    def push(self, head_ref, new_key):
        # allocate node
        new_node = Node()
 
        # put in the key
        new_node.key = new_key
 
        # link the old list of the new node
        new_node.next = head_ref
 
        # move the head to point to the new node
        head_ref = new_node
        return head_ref
 
    @staticmethod
    def printRandom(head):
        temp = head
        v = []
        while temp != None:
            v.append(temp.key)
            temp = temp.next
        n = len(v)
        randIndex = random.randint(0, n-1)
        print(v[randIndex])
 
# Driver's code
if __name__ == '__main__':
    n1 = Node()
    head = None
    head = n1.push(head, 5)
    head = n1.push(head, 20)
    head = n1.push(head, 4)
    head = n1.push(head, 3)
    head = n1.push(head, 30)
    # function call
    Node.printRandom(head)

C#

using System;
using System.Collections.Generic;
 
// Node of Linkedlist
public class Node {
    public int key;
    public Node next;
    public Node(int key)
    {
        this.key = key;
        this.next = null;
    }
}
 
public class GFG {
    // Function to Print Random Values
    public static void printRandom(Node head)
    {
        Node temp = head;
        List<int> list = new List<int>();
        while (temp != null) {
            list.Add(temp.key);
            temp = temp.next;
        }
        int n = list.Count;
        Random rand = new Random();
        int randIndex = rand.Next(n);
        Console.WriteLine(list[randIndex]);
    }
 
    // Drivers Code
    public static void Main()
    {
        // Making List
        Node head = new Node(30);
        head.next = new Node(3);
        head.next.next = new Node(4);
        head.next.next.next = new Node(20);
        head.next.next.next.next = new Node(5);
 
        // Calling Function
        printRandom(head);
    }
}

Javascript

// import random
const val = 7;
 
// Link list node
class Node{
   
    constructor(){
        this.key = 0;
        this.next = null;
    }
 
 
    push(head_ref, new_key){
        // allocate node
        let new_node = new Node();
 
        // put in the key
        new_node.key = new_key;
 
        // link the old list of the new node
        new_node.next = head_ref;
 
        // move the head to point to the new node
        head_ref = new_node;
        return head_ref;
    }
 
 
    printRandom(head){
        let temp = head;
        let v = [];
        while(temp != null){
            v.push(temp.key);
            temp = temp.key;
        }
 
        let n = v.length;
         
        let randIndex = Math.floor((Math.random() * (n-1)));
        console.log(Math.floor(v[randIndex]/val));   
    }
 
}
 
 
// Driver's code
n1 = new Node()
head = null
head = n1.push(head, 5)
head = n1.push(head, 20)
head = n1.push(head, 4)
head = n1.push(head, 3)
head = n1.push(head, 30)
// function call
n1.printRandom(head)
 
// The code is contributed by Nidhi goel.

Output

Complexity Analysis:
Time Complexity: O(n).
Space Complexity:O(n).

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!

Last Updated : 13 Apr, 2023