Posted on by Kalkicode
Code Probability

# Select a random node from a singly linked list

Here given code implementation process.

``````//  C program for
//  Select a random node from a singly linked list
//  using 1/n probability
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
{
int data;
};
struct SingleLL
{
};
// Returns the new linked list
{
// Create memory of head and tail Nodes
struct SingleLL *sll =
(struct SingleLL *) malloc(sizeof(struct SingleLL));
if (sll == NULL)
{
printf("Memory overflow\n");
}
else
{
}
return sll;
}
void addNode(struct SingleLL *sll, int data)
{
// Create dynamic node
if (node == NULL)
{
return;
}
else
{
// Set initial node value
node->data = data;
node->next = NULL;
}
{
}
else
{
sll->tail->next = node;
}
sll->tail = node;
}
{
if (node == NULL)
{
return;
}
while (temp != NULL)
{
printf(" %d →", temp->data);
// Visit to next node
temp = temp->next;
}
printf(" NULL\n");
}
{

struct LinkNode * temp = node;

struct LinkNode * result = node;

int n = 2;

while(temp != NULL)
{
if(rand() % n == 0)
{
// Get new resultant node
result = temp;
}
// visit to next node
temp = temp -> next;

// increase the value of n by one
n++;
}

if(result==NULL)
{
printf("\n None \n");

}
else
{
printf(" Result : %d \n", result->data);
}

}
int main(int argc, char const *argv[])
{
srand(time(NULL));

//  5 → 2 → -2 → 1 → 3 → 6 → NULL
//  -1 → 7 → 5 → 8 → 9 → -9 → 10 → NULL
// Test in first LL
// Test in second LL

return 0;
}``````

#### Output

`````` 5 → 2 → -2 → 1 → 3 → 6 → NULL
Result : 5
Result : 1
Result : 2
-1 → 7 → 5 → 8 → 9 → -9 → 10 → NULL
Result : 9
Result : -1``````
``````import java.util.Random;
/*
Java Program for
Find a peak element in matrix
*/
{
public int data;
{
this.data = data;
this.next = null;
}
}
public class SingleLL
{
public SingleLL()
{
this.tail = null;
}
{
{
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
public void display()
{
{
return;
}
while (temp != null)
{
System.out.print(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
System.out.print(" NULL\n");
}
public int randomValue()
{
Random rand = new Random();
int x = rand.nextInt();
if (x < 0)
{
return -x;
}
return x;
}
public void randomNode()
{
int n = 2;
while (temp != null)
{
if (randomValue() % n == 0)
{
// Get new resultant node
result = temp;
}
// visit to next node
temp = temp.next;
// increase the value of n by one
n++;
}
if (result == null)
{
System.out.print("\n None \n");
}
else
{
System.out.println(" Result : " + result.data);
}
}
public static void main(String[] args)
{
SingleLL sll1 = new SingleLL();
SingleLL sll2 = new SingleLL();
//  5 → 2 → -2 → 1 → 3 → 6 → NULL
//  -1 → 7 → 5 → 8 → 9 → -9 → 10 → NULL
// Test in first LL
sll1.display();
sll1.randomNode();
sll1.randomNode();
sll1.randomNode();
// Test in second LL
sll2.display();
sll2.randomNode();
sll2.randomNode();
}
}``````

#### Output

`````` 5 → 2 → -2 → 1 → 3 → 6 → NULL
Result : 6
Result : 3
Result : 5
-1 → 7 → 5 → 8 → 9 → -9 → 10 → NULL
Result : 7
Result : -9``````
``````// Include header file
#include <iostream>
#include <time.h>
#include <stdlib.h>
using namespace std;
/*
C++ Program for
Find a peak element in matrix
*/
{
public: int data;
{
this->data = data;
this->next = NULL;
}
};
class SingleLL
{
SingleLL()
{
this->tail = NULL;
}
{
{
}
else
{
// Append the node at last position
this->tail->next = node;
}
this->tail = node;
}
void display()
{
{
return;
}
while (temp != NULL)
{
cout << " " << temp->data << " →";
// Visit to next node
temp = temp->next;
}
cout << " NULL\n";
}
int randomValue()
{

int x = rand();
if (x < 0)
{
return -x;
}
return x;
}
void randomNode()
{
int n = 2;
while (temp != NULL)
{
if (this->randomValue() % n == 0)
{
// Get new resultant node
result = temp;
}
// visit to next node
temp = temp->next;
// increase the value of n by one
n++;
}
if (result == NULL)
{
cout << "\n None \n";
}
else
{
cout << " Result : " << result->data << endl;
}
}
};
int main()
{
srand(time(NULL));
SingleLL *sll1 = new SingleLL();
SingleLL *sll2 = new SingleLL();
//  5 → 2 → -2 → 1 → 3 → 6 → NULL
//  -1 → 7 → 5 → 8 → 9 → -9 → 10 → NULL
// Test in first LL
sll1->display();
sll1->randomNode();
sll1->randomNode();
sll1->randomNode();
// Test in second LL
sll2->display();
sll2->randomNode();
sll2->randomNode();
return 0;
}``````

#### Output

`````` 5 → 2 → -2 → 1 → 3 → 6 → NULL
Result : 6
Result : -2
Result : 5
-1 → 7 → 5 → 8 → 9 → -9 → 10 → NULL
Result : 8
Result : -9``````
``````// Include namespace system
using System;
/*
Csharp Program for
Find a peak element in matrix
*/
{
public int data;
{
this.data = data;
this.next = null;
}
}
public class SingleLL
{
public SingleLL()
{
this.tail = null;
}
{
{
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
public void display()
{
{
return;
}
while (temp != null)
{
Console.Write(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
Console.Write(" NULL\n");
}
public int randomValue()
{
Random rand = new Random();
int x = rand.Next();
if (x < 0)
{
return -x;
}
return x;
}
public void randomNode()
{
int n = 2;
while (temp != null)
{
if (this.randomValue() % n == 0)
{
// Get new resultant node
result = temp;
}
// visit to next node
temp = temp.next;
// increase the value of n by one
n++;
}
if (result == null)
{
Console.Write("\n None \n");
}
else
{
Console.WriteLine(" Result : " + result.data);
}
}
public static void Main(String[] args)
{
SingleLL sll1 = new SingleLL();
SingleLL sll2 = new SingleLL();
//  5 → 2 → -2 → 1 → 3 → 6 → NULL
//  -1 → 7 → 5 → 8 → 9 → -9 → 10 → NULL
// Test in first LL
sll1.display();
sll1.randomNode();
sll1.randomNode();
sll1.randomNode();
// Test in second LL
sll2.display();
sll2.randomNode();
sll2.randomNode();
}
}``````

#### Output

`````` 5 → 2 → -2 → 1 → 3 → 6 → NULL
Result : 3
Result : 1
Result : 3
-1 → 7 → 5 → 8 → 9 → -9 → 10 → NULL
Result : 9
Result : -1``````
``````package main

import (
"fmt"
"math/rand"
"math"
"time"
)
/*
Go Program for
Find a peak element in matrix
*/
data int
}
me.data = data
me.next = nil
return me
}
type SingleLL struct {
}
func getSingleLL() * SingleLL {
var me *SingleLL = &SingleLL {}
me.tail = nil
return me
}
} else {
// Append the node at last position
this.tail.next = node
}
this.tail = node
}
func(this SingleLL) display() {
return
}
for (temp != nil) {
fmt.Print(" ", temp.data, " →")
// Visit to next node
temp = temp.next
}
fmt.Print(" NULL\n")
}

func(this SingleLL) randomNode() {
var n int = 2
rand.Seed(time.Now().UnixNano())
for (temp != nil) {
if rand.Intn(math.MaxInt64-1) % n == 0 {
// Get new resultant node
result = temp
}
// visit to next node
temp = temp.next
// increase the value of n by one
n++
}
if result == nil {
fmt.Print("\n None \n")
} else {
fmt.Println(" Result : ", result.data)
}
}
func main() {
var sll1 * SingleLL = getSingleLL()
var sll2 * SingleLL = getSingleLL()
//  5 → 2 → -2 → 1 → 3 → 6 → NULL
//  -1 → 7 → 5 → 8 → 9 → -9 → 10 → NULL
// Test in first LL
sll1.display()
sll1.randomNode()
sll1.randomNode()
sll1.randomNode()
// Test in second LL
sll2.display()
sll2.randomNode()
sll2.randomNode()
}``````

#### Output

`````` 5 → 2 → -2 → 1 → 3 → 6 → NULL
Result :  3
Result :  6
Result :  5
-1 → 7 → 5 → 8 → 9 → -9 → 10 → NULL
Result :  -1
Result :  10
``````
``````<?php
/*
Php Program for
Find a peak element in matrix
*/
{
public \$data;
public \$next;
public	function __construct(\$data)
{
\$this->data = \$data;
\$this->next = NULL;
}
}
class SingleLL
{
public \$tail;
public	function __construct()
{
\$this->tail = NULL;
}
{
{
}
else
{
// Append the node at last position
\$this->tail->next = \$node;
}
\$this->tail = \$node;
}
public	function display()
{
{
return;
}
while (\$temp != NULL)
{
echo(" ".\$temp->data." →");
// Visit to next node
\$temp = \$temp->next;
}
echo(" NULL\n");
}
public	function randomValue()
{
\$x = rand();
if (\$x < 0)
{
return -\$x;
}
return \$x;
}
public	function randomNode()
{
\$n = 2;
while (\$temp != NULL)
{
if (\$this->randomValue() % \$n == 0)
{
// Get new resultant node
\$result = \$temp;
}
// visit to next node
\$temp = \$temp->next;
// increase the value of n by one
\$n++;
}
if (\$result == NULL)
{
echo("\n None \n");
}
else
{
echo(" Result : ".\$result->data."\n");
}
}
}

function main()
{
\$sll1 = new SingleLL();
\$sll2 = new SingleLL();
//  5 → 2 → -2 → 1 → 3 → 6 → NULL
//  -1 → 7 → 5 → 8 → 9 → -9 → 10 → NULL
// Test in first LL
\$sll1->display();
\$sll1->randomNode();
\$sll1->randomNode();
\$sll1->randomNode();
// Test in second LL
\$sll2->display();
\$sll2->randomNode();
\$sll2->randomNode();
}
main();``````

#### Output

`````` 5 → 2 → -2 → 1 → 3 → 6 → NULL
Result : 5
Result : 3
Result : -2
-1 → 7 → 5 → 8 → 9 → -9 → 10 → NULL
Result : 8
Result : 5``````
``````/*
Node JS Program for
Find a peak element in matrix
*/
{
constructor(data)
{
this.data = data;
this.next = null;
}
}
class SingleLL
{
constructor()
{
this.tail = null;
}
{
{
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
display()
{
{
return;
}
while (temp != null)
{
process.stdout.write(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
process.stdout.write(" NULL\n");
}
randomValue()
{
var x = Math.floor(Math.random() * Math.floor(100000));
if (x < 0)
{
return -x;
}
return x;
}
randomNode()
{
var n = 2;
while (temp != null)
{
if (this.randomValue() % n == 0)
{
// Get new resultant node
result = temp;
}
// visit to next node
temp = temp.next;
// increase the value of n by one
n++;
}
if (result == null)
{
process.stdout.write("\n None \n");
}
else
{
console.log(" Result : " + result.data);
}
}
}

function main()
{
var sll1 = new SingleLL();
var sll2 = new SingleLL();
//  5 → 2 → -2 → 1 → 3 → 6 → NULL
//  -1 → 7 → 5 → 8 → 9 → -9 → 10 → NULL
// Test in first LL
sll1.display();
sll1.randomNode();
sll1.randomNode();
sll1.randomNode();
// Test in second LL
sll2.display();
sll2.randomNode();
sll2.randomNode();
}
main();``````

#### Output

`````` 5 → 2 → -2 → 1 → 3 → 6 → NULL
Result : 5
Result : 1
Result : 3
-1 → 7 → 5 → 8 → 9 → -9 → 10 → NULL
Result : 9
Result : -1``````
``````#    Python 3 Program for
#    Find a peak element in matrix
import random
import sys
def __init__(self, data) :
self.data = data
self.next = None

class SingleLL :
def __init__(self) :
self.tail = None

else :
#  Append the node at last position
self.tail.next = node

self.tail = node

def display(self) :
return

while (temp != None) :
print("", temp.data ," →", end = "")
#  Visit to next node
temp = temp.next

print(" NULL")

def randomValue(self) :
x = random.randint(0,sys.maxsize-2)
if (x < 0) :
return -x

return x

def randomNode(self) :
n = 2
while (temp != None) :
if (self.randomValue() % n == 0) :
#  Get new resultant node
result = temp

#  visit to next node
temp = temp.next
#  increase the value of n by one
n += 1

if (result == None) :
print("\n None ")
else :
print(" Result : ", result.data)

def main() :
sll1 = SingleLL()
sll2 = SingleLL()
#   5 → 2 → -2 → 1 → 3 → 6 → NULL
#   -1 → 7 → 5 → 8 → 9 → -9 → 10 → NULL
#  Test in first LL
sll1.display()
sll1.randomNode()
sll1.randomNode()
sll1.randomNode()
#  Test in second LL
sll2.display()
sll2.randomNode()
sll2.randomNode()

if __name__ == "__main__": main()``````

#### Output

`````` 5  → 2  → -2  → 1  → 3  → 6  → NULL
Result :  6
Result :  2
Result :  -2
-1  → 7  → 5  → 8  → 9  → -9  → 10  → NULL
Result :  5
Result :  5``````
``````#    Ruby Program for
#    Find a peak element in matrix

attr_accessor :data, :next
def initialize(data)
self.data = data
self.next = nil
end

end

class SingleLL
# Define the accessor and reader of class SingleLL
def initialize()
self.tail = nil
end

else

#  Append the node at last position
self.tail.next = node
end

self.tail = node
end

def display()
return
end

while (temp != nil)
print(" ", temp.data ," →")
#  Visit to next node
temp = temp.next
end

print(" NULL\n")
end

def randomValue()
r = Random.new
max_int = (2**(0.size * 8 -2) -1)
x = r.rand(0...max_int)
if (x < 0)
return -x
end

return x
end

def randomNode()
n = 2
while (temp != nil)
if (self.randomValue() % n == 0)
#  Get new resultant node
result = temp
end

#  visit to next node
temp = temp.next
#  increase the value of n by one
n += 1
end

if (result == nil)
print("\n None \n")
else

print(" Result : ", result.data, "\n")
end

end

end

def main()
sll1 = SingleLL.new()
sll2 = SingleLL.new()
#   5 → 2 → -2 → 1 → 3 → 6 → NULL
#   -1 → 7 → 5 → 8 → 9 → -9 → 10 → NULL
#  Test in first LL
sll1.display()
sll1.randomNode()
sll1.randomNode()
sll1.randomNode()
#  Test in second LL
sll2.display()
sll2.randomNode()
sll2.randomNode()
end

main()``````

#### Output

`````` 5 → 2 → -2 → 1 → 3 → 6 → NULL
Result : -2
Result : 3
Result : 6
-1 → 7 → 5 → 8 → 9 → -9 → 10 → NULL
Result : -1
Result : 7
``````
``````/*
Scala Program for
Find a peak element in matrix
*/
{
def this(data: Int)
{
this(data, null)
}
}
{
def this()
{
this(null, null)
}
def addNode(data: Int): Unit = {
{
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
def display(): Unit = {
{
return;
}
while (temp != null)
{
print(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
print(" NULL\n");
}
def randomValue(): Int = {
var rand = new scala.util.Random;
var x: Int = rand.nextInt();
if (x < 0)
{
return -x;
}
return x;
}
def randomNode(): Unit = {
var n: Int = 2;
while (temp != null)
{
if (randomValue() % n == 0)
{
// Get new resultant node
result = temp;
}
// visit to next node
temp = temp.next;
// increase the value of n by one
n += 1;
}
if (result == null)
{
print("\n None \n");
}
else
{
println(" Result : " + result.data);
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var sll1: SingleLL = new SingleLL();
var sll2: SingleLL = new SingleLL();
//  5 → 2 → -2 → 1 → 3 → 6 → NULL
//  -1 → 7 → 5 → 8 → 9 → -9 → 10 → NULL
// Test in first LL
sll1.display();
sll1.randomNode();
sll1.randomNode();
sll1.randomNode();
// Test in second LL
sll2.display();
sll2.randomNode();
sll2.randomNode();
}
}``````

#### Output

`````` 5 → 2 → -2 → 1 → 3 → 6 → NULL
Result : -2
Result : 3
Result : 5
-1 → 7 → 5 → 8 → 9 → -9 → 10 → NULL
Result : 9
Result : 10``````
``````/*
Swift 4 Program for
Find a peak element in matrix
*/
import Foundation

#if os(Linux)
srandom(UInt32(time(nil)))
#endif
{
var data: Int;
init(_ data: Int)
{
self.data = data;
self.next = nil;
}
}
class SingleLL
{
init()
{
self.tail = nil;
}
{
{
}
else
{
// Append the node at last position
self.tail!.next = node;
}
self.tail = node;
}
func display()
{
{
return;
}
while (temp  != nil)
{
print(" ", temp!.data ," →", terminator: "");
// Visit to next node
temp = temp!.next;
}
print(" NULL");
}
func randomValue() -> Int
{
var x: Int = 0;
let max_value = UInt8.max-1 ;
//Get new rand number
#if os(Linux)
x = Int(random())
#else
x = Int(arc4random_uniform(UInt32(max_value)))
#endif
if(x < 0)
{
return -x;
}
return x;
}
func randomNode()
{
var n: Int = 2;
while (temp  != nil)
{
if (self.randomValue() % n == 0)
{
// Get new resultant node
result = temp;
}
// visit to next node
temp = temp!.next;
// increase the value of n by one
n += 1;
}
if (result == nil)
{
print("\n None ");
}
else
{
print(" Result : ", result!.data);
}
}
}
func main()
{
let sll1: SingleLL = SingleLL();
let sll2: SingleLL = SingleLL();
//  5 → 2 → -2 → 1 → 3 → 6 → NULL
//  -1 → 7 → 5 → 8 → 9 → -9 → 10 → NULL
// Test in first LL
sll1.display();
sll1.randomNode();
sll1.randomNode();
sll1.randomNode();
// Test in second LL
sll2.display();
sll2.randomNode();
sll2.randomNode();
}
main();``````

#### Output

``````  5  →  2  →  -2  →  1  →  3  →  6  → NULL
Result :  3
Result :  -2
Result :  2
-1  →  7  →  5  →  8  →  9  →  -9  →  10  → NULL
Result :  7
Result :  9``````
``````/*
Kotlin Program for
Find a peak element in matrix
*/

{
var data: Int;
constructor(data: Int)
{
this.data = data;
this.next = null;
}
}
class SingleLL
{
constructor()
{
this.tail = null;
}
{
{
}
else
{
// Append the node at last position
this.tail?.next = node;
}
this.tail = node;
}
fun display(): Unit
{
{
return;
}
while (temp != null)
{
print(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
print(" NULL\n");
}
fun randomValue(): Int
{
var x: Int = (0..Int.MAX_VALUE).random()
return x;
}
fun randomNode(): Unit
{
var n: Int = 2;
while (temp != null)
{
if (this.randomValue() % n == 0)
{
// Get new resultant node
result = temp;
}
// visit to next node
temp = temp.next;
// increase the value of n by one
n += 1;
}
if (result == null)
{
print("\n None \n");
}
else
{
println(" Result : " + result.data);
}
}
}
fun main(args: Array < String > ): Unit
{
val sll1: SingleLL = SingleLL();
val sll2: SingleLL = SingleLL();
//  5 → 2 → -2 → 1 → 3 → 6 → NULL
//  -1 → 7 → 5 → 8 → 9 → -9 → 10 → NULL
// Test in first LL
sll1.display();
sll1.randomNode();
sll1.randomNode();
sll1.randomNode();
// Test in second LL
sll2.display();
sll2.randomNode();
sll2.randomNode();
}``````

#### Output

`````` 5 → 2 → -2 → 1 → 3 → 6 → NULL
Result : 3
Result : 6
Result : 5
-1 → 7 → 5 → 8 → 9 → -9 → 10 → NULL
Result : -1
Result : 5``````

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post