Next greater node in linked list
Here given code implementation process.
// C Program
// Next greater node in linked list
#include <stdio.h>
#include <stdlib.h> //for malloc function
// Linked List LinkNode
struct LinkNode
{
int data;
struct LinkNode *next;
};
// Singly linked list
struct SingleLL
{
struct LinkNode *head;
struct LinkNode *tail;
};
// Returns the new linked list
struct SingleLL *newLinkedList()
{
// Create memory of head and tail Nodes
struct SingleLL *sll = (struct SingleLL *) malloc(sizeof(struct SingleLL));
if (sll == NULL)
{
printf("Memory overflow\n");
}
else
{
sll->head = NULL;
sll->tail = NULL;
}
return sll;
}
// Returns a new Node of linked list
struct LinkNode *createLinkNode(int data)
{
// Create dynamic node
struct LinkNode *node = (struct LinkNode *) malloc(sizeof(struct LinkNode));
if (node == NULL)
{
printf("Memory overflow\n");
}
else
{
// Set initial node value
node->data = data;
node->next = NULL;
}
return node;
}
// Add new Node at end of linked list
void addNode(struct SingleLL *sll, int data)
{
struct LinkNode *node = createLinkNode(data);
if (sll->head == NULL)
{
sll->head = node;
}
else
{
// Append the node at last position
sll->tail->next = node;
}
sll->tail = node;
}
// Display linked list element
void display(struct SingleLL *sll)
{
if (sll->head == NULL)
{
printf("\n Empty linked list\n");
return;
}
struct LinkNode *temp = sll->head;
// iterating linked list elements
while (temp != NULL)
{
printf(" %d →", temp->data);
// Visit to next node
temp = temp->next;
}
printf(" NULL\n");
}
// Change each node of linked from next largest node
void nextLargest(struct SingleLL *sll)
{
if (sll->head == NULL)
{
printf("\n Empty linked list\n");
return;
}
struct LinkNode *start = sll->head;
struct LinkNode *temp = NULL;
// Execute linked list
while (start != NULL)
{
temp = start->next;
// Finding next largest node
while (temp != NULL && temp->data < start->data)
{
// Visit to next node
temp = temp->next;
}
if (temp != NULL)
{
// Change node value
start->data = temp->data;
}
else
{
// When next largest node are not found
start->data = 0;
}
// Visit to next node
start = start->next;
}
}
int main()
{
// Create a empty linked list
struct SingleLL *sll = newLinkedList();
// Constructed linked list
// 4 → 2 → -7 → 3 → 9 → 1 → 4 → 10 → 8 →NULL
addNode(sll, 4);
addNode(sll, 2);
addNode(sll, -7);
addNode(sll, 3);
addNode(sll, 9);
addNode(sll, 1);
addNode(sll, 4);
addNode(sll, 10);
addNode(sll, 8);
printf("\n Before Convert \n");
display(sll);
nextLargest(sll);
// 9 → 3 → 3 → 9 → 10 → 4 → 10 → 0 → 0 → NULL
printf("\n After Convert \n");
display(sll);
return 0;
}
Output
Before Convert
4 → 2 → -7 → 3 → 9 → 1 → 4 → 10 → 8 → NULL
After Convert
9 → 3 → 3 → 9 → 10 → 4 → 10 → 0 → 0 → NULL
/*
Java Program for
Next greater node in linked list
*/
// Linked list node
class LinkNode
{
public int data;
public LinkNode next;
public LinkNode(int data)
{
this.data = data;
this.next = null;
}
}
public class SingleLL
{
public LinkNode head;
public LinkNode tail;
public SingleLL()
{
this.head = null;
this.tail = null;
}
//Add new Node at end of linked list
public void addNode(int data)
{
LinkNode node = new LinkNode(data);
if (this.head == null)
{
this.head = node;
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
// Display linked list element
public void display()
{
if (this.head == null)
{
System.out.print("\n Empty linked list\n");
return;
}
LinkNode temp = this.head;
//iterating linked list elements
while (temp != null)
{
System.out.print(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
System.out.print(" NULL\n");
}
// Change each node of linked from next largest node
public void nextLargest()
{
if (this.head == null)
{
System.out.print("\n Empty linked list\n");
return;
}
LinkNode start = this.head;
LinkNode auxiliary = null;
// Execute linked list
while (start != null)
{
auxiliary = start.next;
// Finding next largest node
while (auxiliary != null && auxiliary.data < start.data)
{
// Visit to next node
auxiliary = auxiliary.next;
}
if (auxiliary != null)
{
// Change node value
start.data = auxiliary.data;
}
else
{
// When next largest node are not found
start.data = 0;
}
// Visit to next node
start = start.next;
}
}
public static void main(String[] args)
{
// Create a empty linked list
SingleLL sll = new SingleLL();
// Constructed linked list
// 4 → 2 → -7 → 3 → 9 → 1 → 4 → 10 → 8 →NULL
sll.addNode(4);
sll.addNode(2);
sll.addNode(-7);
sll.addNode(3);
sll.addNode(9);
sll.addNode(1);
sll.addNode(4);
sll.addNode(10);
sll.addNode(8);
System.out.print("\n Before Convert \n");
sll.display();
sll.nextLargest();
// After convert linked list
// 9 → 3 → 3 → 9 → 10 → 4 → 10 → 0 → 0 → NULL
System.out.print("\n After Convert \n");
sll.display();
}
}
Output
Before Convert
4 → 2 → -7 → 3 → 9 → 1 → 4 → 10 → 8 → NULL
After Convert
9 → 3 → 3 → 9 → 10 → 4 → 10 → 0 → 0 → NULL
// Include header file
#include <iostream>
using namespace std;
/*
C++ Program for
Next greater node in linked list
*/
// Linked list node
class LinkNode
{
public:
int data;
LinkNode *next;
LinkNode(int data)
{
this->data = data;
this->next = NULL;
}
};
class SingleLL
{
public:
LinkNode *head;
LinkNode *tail;
SingleLL()
{
this->head = NULL;
this->tail = NULL;
}
//Add new Node at end of linked list
void addNode(int data)
{
LinkNode *node = new LinkNode(data);
if (this->head == NULL)
{
this->head = node;
}
else
{
// Append the node at last position
this->tail->next = node;
}
this->tail = node;
}
// Display linked list element
void display()
{
if (this->head == NULL)
{
cout << "\n Empty linked list\n";
return;
}
LinkNode *temp = this->head;
//iterating linked list elements
while (temp != NULL)
{
cout << " " << temp->data << " →";
// Visit to next node
temp = temp->next;
}
cout << " NULL\n";
}
// Change each node of linked from next largest node
void nextLargest()
{
if (this->head == NULL)
{
cout << "\n Empty linked list\n";
return;
}
LinkNode *start = this->head;
LinkNode *auxiliary = NULL;
// Execute linked list
while (start != NULL)
{
auxiliary = start->next;
// Finding next largest node
while (auxiliary != NULL && auxiliary->data < start->data)
{
// Visit to next node
auxiliary = auxiliary->next;
}
if (auxiliary != NULL)
{
// Change node value
start->data = auxiliary->data;
}
else
{
// When next largest node are not found
start->data = 0;
}
// Visit to next node
start = start->next;
}
}
};
int main()
{
// Create a empty linked list
SingleLL sll = SingleLL();
// Constructed linked list
// 4 → 2 → -7 → 3 → 9 → 1 → 4 → 10 → 8 →NULL
sll.addNode(4);
sll.addNode(2);
sll.addNode(-7);
sll.addNode(3);
sll.addNode(9);
sll.addNode(1);
sll.addNode(4);
sll.addNode(10);
sll.addNode(8);
cout << "\n Before Convert \n";
sll.display();
sll.nextLargest();
// After convert linked list
// 9 → 3 → 3 → 9 → 10 → 4 → 10 → 0 → 0 → NULL
cout << "\n After Convert \n";
sll.display();
return 0;
}
Output
Before Convert
4 → 2 → -7 → 3 → 9 → 1 → 4 → 10 → 8 → NULL
After Convert
9 → 3 → 3 → 9 → 10 → 4 → 10 → 0 → 0 → NULL
// Include namespace system
using System;
/*
C# Program for
Next greater node in linked list
*/
// Linked list node
public class LinkNode
{
public int data;
public LinkNode next;
public LinkNode(int data)
{
this.data = data;
this.next = null;
}
}
public class SingleLL
{
public LinkNode head;
public LinkNode tail;
public SingleLL()
{
this.head = null;
this.tail = null;
}
//Add new Node at end of linked list
public void addNode(int data)
{
LinkNode node = new LinkNode(data);
if (this.head == null)
{
this.head = node;
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
// Display linked list element
public void display()
{
if (this.head == null)
{
Console.Write("\n Empty linked list\n");
return;
}
LinkNode temp = this.head;
//iterating linked list elements
while (temp != null)
{
Console.Write(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
Console.Write(" NULL\n");
}
// Change each node of linked from next largest node
public void nextLargest()
{
if (this.head == null)
{
Console.Write("\n Empty linked list\n");
return;
}
LinkNode start = this.head;
LinkNode auxiliary = null;
// Execute linked list
while (start != null)
{
auxiliary = start.next;
// Finding next largest node
while (auxiliary != null && auxiliary.data < start.data)
{
// Visit to next node
auxiliary = auxiliary.next;
}
if (auxiliary != null)
{
// Change node value
start.data = auxiliary.data;
}
else
{
// When next largest node are not found
start.data = 0;
}
// Visit to next node
start = start.next;
}
}
public static void Main(String[] args)
{
// Create a empty linked list
SingleLL sll = new SingleLL();
// Constructed linked list
// 4 → 2 → -7 → 3 → 9 → 1 → 4 → 10 → 8 →NULL
sll.addNode(4);
sll.addNode(2);
sll.addNode(-7);
sll.addNode(3);
sll.addNode(9);
sll.addNode(1);
sll.addNode(4);
sll.addNode(10);
sll.addNode(8);
Console.Write("\n Before Convert \n");
sll.display();
sll.nextLargest();
// After convert linked list
// 9 → 3 → 3 → 9 → 10 → 4 → 10 → 0 → 0 → NULL
Console.Write("\n After Convert \n");
sll.display();
}
}
Output
Before Convert
4 → 2 → -7 → 3 → 9 → 1 → 4 → 10 → 8 → NULL
After Convert
9 → 3 → 3 → 9 → 10 → 4 → 10 → 0 → 0 → NULL
<?php
/*
Php Program for
Next greater node in linked list
*/
// Linked list node
class LinkNode
{
public $data;
public $next;
function __construct($data)
{
$this->data = $data;
$this->next = null;
}
}
class SingleLL
{
public $head;
public $tail;
function __construct()
{
$this->head = null;
$this->tail = null;
}
//Add new Node at end of linked list
public function addNode($data)
{
$node = new LinkNode($data);
if ($this->head == null)
{
$this->head = $node;
}
else
{
// Append the node at last position
$this->tail->next = $node;
}
$this->tail = $node;
}
// Display linked list element
public function display()
{
if ($this->head == null)
{
echo "\n Empty linked list\n";
return;
}
$temp = $this->head;
//iterating linked list elements
while ($temp != null)
{
echo " ". $temp->data ." →";
// Visit to next node
$temp = $temp->next;
}
echo " NULL\n";
}
// Change each node of linked from next largest node
public function nextLargest()
{
if ($this->head == null)
{
echo "\n Empty linked list\n";
return;
}
$start = $this->head;
$auxiliary = null;
// Execute linked list
while ($start != null)
{
$auxiliary = $start->next;
// Finding next largest node
while ($auxiliary != null && $auxiliary->data < $start->data)
{
// Visit to next node
$auxiliary = $auxiliary->next;
}
if ($auxiliary != null)
{
// Change node value
$start->data = $auxiliary->data;
}
else
{
// When next largest node are not found
$start->data = 0;
}
// Visit to next node
$start = $start->next;
}
}
}
function main()
{
// Create a empty linked list
$sll = new SingleLL();
// Constructed linked list
// 4 → 2 → -7 → 3 → 9 → 1 → 4 → 10 → 8 →NULL
$sll->addNode(4);
$sll->addNode(2);
$sll->addNode(-7);
$sll->addNode(3);
$sll->addNode(9);
$sll->addNode(1);
$sll->addNode(4);
$sll->addNode(10);
$sll->addNode(8);
echo "\n Before Convert \n";
$sll->display();
$sll->nextLargest();
// After convert linked list
// 9 → 3 → 3 → 9 → 10 → 4 → 10 → 0 → 0 → NULL
echo "\n After Convert \n";
$sll->display();
}
main();
Output
Before Convert
4 → 2 → -7 → 3 → 9 → 1 → 4 → 10 → 8 → NULL
After Convert
9 → 3 → 3 → 9 → 10 → 4 → 10 → 0 → 0 → NULL
/*
Node Js Program for
Next greater node in linked list
*/
// Linked list node
class LinkNode
{
constructor(data)
{
this.data = data;
this.next = null;
}
}
class SingleLL
{
constructor()
{
this.head = null;
this.tail = null;
}
//Add new Node at end of linked list
addNode(data)
{
var node = new LinkNode(data);
if (this.head == null)
{
this.head = node;
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
// Display linked list element
display()
{
if (this.head == null)
{
process.stdout.write("\n Empty linked list\n");
return;
}
var temp = this.head;
//iterating linked list elements
while (temp != null)
{
process.stdout.write(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
process.stdout.write(" NULL\n");
}
// Change each node of linked from next largest node
nextLargest()
{
if (this.head == null)
{
process.stdout.write("\n Empty linked list\n");
return;
}
var start = this.head;
var auxiliary = null;
// Execute linked list
while (start != null)
{
auxiliary = start.next;
// Finding next largest node
while (auxiliary != null && auxiliary.data < start.data)
{
// Visit to next node
auxiliary = auxiliary.next;
}
if (auxiliary != null)
{
// Change node value
start.data = auxiliary.data;
}
else
{
// When next largest node are not found
start.data = 0;
}
// Visit to next node
start = start.next;
}
}
}
function main()
{
// Create a empty linked list
var sll = new SingleLL();
// Constructed linked list
// 4 → 2 → -7 → 3 → 9 → 1 → 4 → 10 → 8 →NULL
sll.addNode(4);
sll.addNode(2);
sll.addNode(-7);
sll.addNode(3);
sll.addNode(9);
sll.addNode(1);
sll.addNode(4);
sll.addNode(10);
sll.addNode(8);
process.stdout.write("\n Before Convert \n");
sll.display();
sll.nextLargest();
// After convert linked list
// 9 → 3 → 3 → 9 → 10 → 4 → 10 → 0 → 0 → NULL
process.stdout.write("\n After Convert \n");
sll.display();
}
main();
Output
Before Convert
4 → 2 → -7 → 3 → 9 → 1 → 4 → 10 → 8 → NULL
After Convert
9 → 3 → 3 → 9 → 10 → 4 → 10 → 0 → 0 → NULL
# Python 3 Program for
# Next greater node in linked list
# Linked list node
class LinkNode :
def __init__(self, data) :
self.data = data
self.next = None
class SingleLL :
def __init__(self) :
self.head = None
self.tail = None
# Add new Node at end of linked list
def addNode(self, data) :
node = LinkNode(data)
if (self.head == None) :
self.head = node
else :
# Append the node at last position
self.tail.next = node
self.tail = node
# Display linked list element
def display(self) :
if (self.head == None) :
print("\n Empty linked list")
return
temp = self.head
# iterating linked list elements
while (temp != None) :
print("", temp.data ,"→", end = "")
# Visit to next node
temp = temp.next
print(" NULL")
# Change each node of linked from next largest node
def nextLargest(self) :
if (self.head == None) :
print("\n Empty linked list")
return
start = self.head
auxiliary = None
# Execute linked list
while (start != None) :
auxiliary = start.next
# Finding next largest node
while (auxiliary != None and auxiliary.data < start.data) :
# Visit to next node
auxiliary = auxiliary.next
if (auxiliary != None) :
# Change node value
start.data = auxiliary.data
else :
# When next largest node are not found
start.data = 0
# Visit to next node
start = start.next
def main() :
# Create a empty linked list
sll = SingleLL()
# Constructed linked list
# 4 → 2 → -7 → 3 → 9 → 1 → 4 → 10 → 8 →NULL
sll.addNode(4)
sll.addNode(2)
sll.addNode(-7)
sll.addNode(3)
sll.addNode(9)
sll.addNode(1)
sll.addNode(4)
sll.addNode(10)
sll.addNode(8)
print("\n Before Convert ")
sll.display()
sll.nextLargest()
# After convert linked list
# 9 → 3 → 3 → 9 → 10 → 4 → 10 → 0 → 0 → NULL
print("\n After Convert ")
sll.display()
if __name__ == "__main__": main()
Output
Before Convert
4 → 2 → -7 → 3 → 9 → 1 → 4 → 10 → 8 → NULL
After Convert
9 → 3 → 3 → 9 → 10 → 4 → 10 → 0 → 0 → NULL
# Ruby Program for
# Next greater node in linked list
# Linked list node
class LinkNode
# Define the accessor and reader of class LinkNode
attr_reader :data, :next
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
attr_reader :head, :tail
attr_accessor :head, :tail
def initialize()
self.head = nil
self.tail = nil
end
# Add new Node at end of linked list
def addNode(data)
node = LinkNode.new(data)
if (self.head == nil)
self.head = node
else
# Append the node at last position
self.tail.next = node
end
self.tail = node
end
# Display linked list element
def display()
if (self.head == nil)
print("\n Empty linked list\n")
return
end
temp = self.head
# iterating linked list elements
while (temp != nil)
print(" ", temp.data ," →")
# Visit to next node
temp = temp.next
end
print(" NULL\n")
end
# Change each node of linked from next largest node
def nextLargest()
if (self.head == nil)
print("\n Empty linked list\n")
return
end
start = self.head
auxiliary = nil
# Execute linked list
while (start != nil)
auxiliary = start.next
# Finding next largest node
while (auxiliary != nil && auxiliary.data < start.data)
# Visit to next node
auxiliary = auxiliary.next
end
if (auxiliary != nil)
# Change node value
start.data = auxiliary.data
else
# When next largest node are not found
start.data = 0
end
# Visit to next node
start = start.next
end
end
end
def main()
# Create a empty linked list
sll = SingleLL.new()
# Constructed linked list
# 4 → 2 → -7 → 3 → 9 → 1 → 4 → 10 → 8 →NULL
sll.addNode(4)
sll.addNode(2)
sll.addNode(-7)
sll.addNode(3)
sll.addNode(9)
sll.addNode(1)
sll.addNode(4)
sll.addNode(10)
sll.addNode(8)
print("\n Before Convert \n")
sll.display()
sll.nextLargest()
# After convert linked list
# 9 → 3 → 3 → 9 → 10 → 4 → 10 → 0 → 0 → NULL
print("\n After Convert \n")
sll.display()
end
main()
Output
Before Convert
4 → 2 → -7 → 3 → 9 → 1 → 4 → 10 → 8 → NULL
After Convert
9 → 3 → 3 → 9 → 10 → 4 → 10 → 0 → 0 → NULL
/*
Scala Program for
Next greater node in linked list
*/
// Linked list node
class LinkNode(var data: Int , var next: LinkNode)
{
def this(data: Int)
{
this(data, null);
}
}
class SingleLL(var head: LinkNode , var tail: LinkNode)
{
def this()
{
this(null, null);
}
//Add new Node at end of linked list
def addNode(data: Int): Unit = {
var node: LinkNode = new LinkNode(data);
if (this.head == null)
{
this.head = node;
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
// Display linked list element
def display(): Unit = {
if (this.head == null)
{
print("\n Empty linked list\n");
return;
}
var temp: LinkNode = this.head;
//iterating linked list elements
while (temp != null)
{
print(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
print(" NULL\n");
}
// Change each node of linked from next largest node
def nextLargest(): Unit = {
if (this.head == null)
{
print("\n Empty linked list\n");
return;
}
var start: LinkNode = this.head;
var auxiliary: LinkNode = null;
// Execute linked list
while (start != null)
{
auxiliary = start.next;
// Finding next largest node
while (auxiliary != null && auxiliary.data < start.data)
{
// Visit to next node
auxiliary = auxiliary.next;
}
if (auxiliary != null)
{
// Change node value
start.data = auxiliary.data;
}
else
{
// When next largest node are not found
start.data = 0;
}
// Visit to next node
start = start.next;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
// Create a empty linked list
var sll: SingleLL = new SingleLL();
// Constructed linked list
// 4 → 2 → -7 → 3 → 9 → 1 → 4 → 10 → 8 →NULL
sll.addNode(4);
sll.addNode(2);
sll.addNode(-7);
sll.addNode(3);
sll.addNode(9);
sll.addNode(1);
sll.addNode(4);
sll.addNode(10);
sll.addNode(8);
print("\n Before Convert \n");
sll.display();
sll.nextLargest();
// After convert linked list
// 9 → 3 → 3 → 9 → 10 → 4 → 10 → 0 → 0 → NULL
print("\n After Convert \n");
sll.display();
}
}
Output
Before Convert
4 → 2 → -7 → 3 → 9 → 1 → 4 → 10 → 8 → NULL
After Convert
9 → 3 → 3 → 9 → 10 → 4 → 10 → 0 → 0 → NULL
/*
Swift 4 Program for
Next greater node in linked list
*/
// Linked list node
class LinkNode
{
var data: Int;
var next: LinkNode? ;
init(_ data: Int)
{
self.data = data;
self.next = nil;
}
}
class SingleLL
{
var head: LinkNode? ;
var tail: LinkNode? ;
init()
{
self.head = nil;
self.tail = nil;
}
//Add new Node at end of linked list
func addNode(_ data: Int)
{
let node: LinkNode? = LinkNode(data);
if (self.head == nil)
{
self.head = node;
}
else
{
// Append the node at last position
self.tail!.next = node;
}
self.tail = node;
}
// Display linked list element
func display()
{
if (self.head == nil)
{
print("\n Empty linked list");
return;
}
var temp: LinkNode? = self.head;
//iterating linked list elements
while (temp != nil)
{
print("", temp!.data ,"→", terminator: "");
// Visit to next node
temp = temp!.next;
}
print(" NULL");
}
// Change each node of linked from next largest node
func nextLargest()
{
if (self.head == nil)
{
print("\n Empty linked list");
return;
}
var start: LinkNode? = self.head;
var auxiliary: LinkNode? = nil;
// Execute linked list
while (start != nil)
{
auxiliary = start!.next;
// Finding next largest node
while (auxiliary != nil && auxiliary!.data < start!.data)
{
// Visit to next node
auxiliary = auxiliary!.next;
}
if (auxiliary != nil)
{
// Change node value
start!.data = auxiliary!.data;
}
else
{
// When next largest node are not found
start!.data = 0;
}
// Visit to next node
start = start!.next;
}
}
}
func main()
{
// Create a empty linked list
let sll: SingleLL = SingleLL();
// Constructed linked list
// 4 → 2 → -7 → 3 → 9 → 1 → 4 → 10 → 8 →NULL
sll.addNode(4);
sll.addNode(2);
sll.addNode(-7);
sll.addNode(3);
sll.addNode(9);
sll.addNode(1);
sll.addNode(4);
sll.addNode(10);
sll.addNode(8);
print("\n Before Convert ");
sll.display();
sll.nextLargest();
// After convert linked list
// 9 → 3 → 3 → 9 → 10 → 4 → 10 → 0 → 0 → NULL
print("\n After Convert ");
sll.display();
}
main();
Output
Before Convert
4 → 2 → -7 → 3 → 9 → 1 → 4 → 10 → 8 → NULL
After Convert
9 → 3 → 3 → 9 → 10 → 4 → 10 → 0 → 0 → NULL
/*
Kotlin Program for
Next greater node in linked list
*/
// Linked list node
class LinkNode
{
var data: Int;
var next: LinkNode ? ;
constructor(data: Int)
{
this.data = data;
this.next = null;
}
}
class SingleLL
{
var head: LinkNode ? ;
var tail: LinkNode ? ;
constructor()
{
this.head = null;
this.tail = null;
}
//Add new Node at end of linked list
fun addNode(data: Int): Unit
{
var node: LinkNode ? = LinkNode(data);
if (this.head == null)
{
this.head = node;
}
else
{
// Append the node at last position
this.tail?.next = node;
}
this.tail = node;
}
// Display linked list element
fun display(): Unit
{
if (this.head == null)
{
print("\n Empty linked list\n");
return;
}
var temp: LinkNode ? = this.head;
//iterating linked list elements
while (temp != null)
{
print(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
print(" NULL\n");
}
// Change each node of linked from next largest node
fun nextLargest(): Unit
{
if (this.head == null)
{
print("\n Empty linked list\n");
return;
}
var start: LinkNode ? = this.head;
var auxiliary: LinkNode ? ;
// Execute linked list
while (start != null)
{
auxiliary = start.next;
// Finding next largest node
while (auxiliary != null && auxiliary.data < start.data)
{
// Visit to next node
auxiliary = auxiliary.next;
}
if (auxiliary != null)
{
// Change node value
start.data = auxiliary.data;
}
else
{
// When next largest node are not found
start.data = 0;
}
// Visit to next node
start = start.next;
}
}
}
fun main(args: Array < String > ): Unit
{
// Create a empty linked list
var sll: SingleLL = SingleLL();
// Constructed linked list
// 4 → 2 → -7 → 3 → 9 → 1 → 4 → 10 → 8 →NULL
sll.addNode(4);
sll.addNode(2);
sll.addNode(-7);
sll.addNode(3);
sll.addNode(9);
sll.addNode(1);
sll.addNode(4);
sll.addNode(10);
sll.addNode(8);
print("\n Before Convert \n");
sll.display();
sll.nextLargest();
// After convert linked list
// 9 → 3 → 3 → 9 → 10 → 4 → 10 → 0 → 0 → NULL
print("\n After Convert \n");
sll.display();
}
Output
Before Convert
4 → 2 → -7 → 3 → 9 → 1 → 4 → 10 → 8 → NULL
After Convert
9 → 3 → 3 → 9 → 10 → 4 → 10 → 0 → 0 → NULL
In above solution tack O(n*n) time. In a better approach we can solve this program using stack in O(n) time..
// C Program
// Next greater node in linked list
// In O(n) Time, by using stack
#include <stdio.h>
#include <stdlib.h> //for malloc function
// Linked List LinkNode
struct LinkNode
{
int data;
struct LinkNode *next;
};
// Singly linked list
struct SingleLL
{
struct LinkNode *head;
struct LinkNode *tail;
};
// Define stack node
struct StackNode
{
int element;
struct StackNode *next;
};
// Define a custom stack
struct MyStack
{
struct StackNode *top;
int size;
};
struct MyStack *newStack()
{
//Make a stack
struct MyStack *stack = (struct MyStack *) malloc(sizeof(struct MyStack));
if (stack != NULL)
{
//Set node values
stack->top = NULL;
stack->size = 0;
}
else
{
printf("\nMemory overflow when create new stack\n");
}
}
// Returns the status of empty or non empty stacks
int isEmpty(struct MyStack *stack)
{
if (stack->size > 0 && stack->top != NULL)
{
return 0;
}
else
{
return 1;
}
}
// Add node at the top of stack
void push(struct MyStack *stack, int element)
{
// Make a new node
struct StackNode *node = (struct StackNode *) malloc(sizeof(struct StackNode));
if (node == NULL)
{
printf("\nMemory overflow when create new stack Node \n");
}
else
{
node->element = element;
node->next = stack->top;
}
// Add stack element
stack->top = node;
stack->size++;
}
// return top element of stack
int peek(struct MyStack *stack)
{
return stack->top->element;
}
// Remove top element of stack
void pop(struct MyStack *stack)
{
if (isEmpty(stack) == 0)
{
struct StackNode *temp = stack->top;
// Change top element of stack
stack->top = temp->next;
// remove previous top
free(temp);
temp = NULL;
stack->size--;
}
}
// Returns the new linked list
struct SingleLL *newLinkedList()
{
// Create memory of head and tail Nodes
struct SingleLL *sll = (struct SingleLL *) malloc(sizeof(struct SingleLL));
if (sll == NULL)
{
printf("Memory overflow\n");
}
else
{
sll->head = NULL;
sll->tail = NULL;
}
return sll;
}
// Returns a new Node of linked list
struct LinkNode *createLinkNode(int data)
{
// Create dynamic node
struct LinkNode *node = (struct LinkNode *) malloc(sizeof(struct LinkNode));
if (node == NULL)
{
printf("Memory overflow\n");
}
else
{
// Set initial node value
node->data = data;
node->next = NULL;
}
return node;
}
// Add new Node at end of linked list
void addNode(struct SingleLL *sll, int data)
{
struct LinkNode *node = createLinkNode(data);
if (sll->head == NULL)
{
sll->head = node;
}
else
{
// Append the node at last position
sll->tail->next = node;
}
sll->tail = node;
}
// Display linked list element
void display(struct SingleLL *sll)
{
if (sll->head == NULL)
{
printf("\n Empty linked list\n");
return;
}
struct LinkNode *temp = sll->head;
// iterating linked list elements
while (temp != NULL)
{
printf(" %d →", temp->data);
// Visit to next node
temp = temp->next;
}
printf(" NULL\n");
}
// reversing the elements of linked list
void reverseElement(struct SingleLL *sll)
{
struct LinkNode *node = sll->head;
struct LinkNode *result = NULL;
struct LinkNode *temp = NULL;
while (node != NULL)
{
temp = node;
node = temp->next;
temp->next = result;
if (result == NULL)
{
// Set new tail node
sll->tail = temp;
}
result = temp;
}
// Set new head
sll->head = result;
}
// Change each node of linked from next largest node
void nextLargest(struct SingleLL *sll)
{
if (sll->head == NULL)
{
printf("\n Empty Linked List ");
}
else
{
// First the reverse all elements of linked list
reverseElement(sll);
struct LinkNode *node = sll->head;
// Create an empty stack
struct MyStack *s = newStack();
while (node != NULL)
{
if (isEmpty(s) == 1)
{
// When stack is empty
push(s, node->data);
node->data = 0;
}
else
{
// Remove all top element of stack which is less than or
// equal to current node value
while (isEmpty(s) == 0 && peek(s) <= node->data)
{
// Remove top of stack
pop(s);
}
if (isEmpty(s) == 1)
{
// After removing top element stack is empty
push(s, node->data);
// When no find largest node in a right side
node->data = 0;
}
else
{
int key = peek(s);
push(s, node->data);
// Set next largest value
node->data = key;
}
}
node = node->next;
}
// Reverse linked list
reverseElement(sll);
}
}
int main()
{
// Create a empty linked list
struct SingleLL *sll = newLinkedList();
// Constructed linked list
// 4 → 2 → -7 → 3 → 9 → 1 → 4 → 10 → 8 →NULL
addNode(sll, 4);
addNode(sll, 2);
addNode(sll, -7);
addNode(sll, 3);
addNode(sll, 9);
addNode(sll, 1);
addNode(sll, 4);
addNode(sll, 10);
addNode(sll, 8);
printf("\n Before Convert \n");
display(sll);
nextLargest(sll);
// 9 → 3 → 3 → 9 → 10 → 4 → 10 → 0 → 0 → NULL
printf("\n After Convert \n");
display(sll);
return 0;
}
Output
Before Convert
4 → 2 → -7 → 3 → 9 → 1 → 4 → 10 → 8 → NULL
After Convert
9 → 3 → 3 → 9 → 10 → 4 → 10 → 0 → 0 → NULL
/*
Java Program for
Next greater node in linked list
In O(n) Time
*/
// Define stack node
class StackNode
{
public int element;
public StackNode next;
public StackNode(int element, StackNode top)
{
this.element = element;
this.next = top;
}
}
// Define a custom stack
class MyStack
{
public StackNode top;
public int size;
public MyStack()
{
//Set node values
this.top = null;
this.size = 0;
}
// Add node at the top of stack
public void push(int element)
{
this.top = new StackNode(element, this.top);
this.size++;
}
public boolean isEmpty()
{
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
public void pop()
{
if (this.size > 0 && this.top != null)
{
StackNode temp = this.top;
// Change top element of stack
this.top = temp.next;
// remove previous top
temp = null;
this.size--;
}
}
// return top element of stack
public int peek()
{
if (this.top == null)
{
return -1;
}
return this.top.element;
}
}
// Linked list node
class LinkNode
{
public int data;
public LinkNode next;
public LinkNode(int data)
{
this.data = data;
this.next = null;
}
}
public class SingleLL
{
public LinkNode head;
public LinkNode tail;
public SingleLL()
{
this.head = null;
this.tail = null;
}
//Add new Node at end of linked list
public void addNode(int data)
{
LinkNode node = new LinkNode(data);
if (this.head == null)
{
this.head = node;
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
// Display linked list element
public void display()
{
if (this.head == null)
{
System.out.print("\n Empty linked list\n");
return;
}
LinkNode temp = this.head;
//iterating linked list elements
while (temp != null)
{
System.out.print(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
System.out.print(" NULL\n");
}
// reversing the elements of linked list
public void reverseElement()
{
LinkNode node = this.head;
LinkNode result = null;
LinkNode temp = null;
while (node != null)
{
temp = node;
node = temp.next;
temp.next = result;
if (result == null)
{
// Set new tail node
this.tail = temp;
}
result = temp;
}
// Set new head
this.head = result;
}
// Change each node of linked from next largest node
public void nextLargest()
{
if (this.head == null)
{
System.out.print("\n Empty Linked List ");
}
else
{
// First the reverse all elements of linked list
this.reverseElement();
LinkNode node = this.head;
// Create an empty stack
MyStack s = new MyStack();
// iterate linked list node
while (node != null)
{
if (s.isEmpty() == true)
{
// When stack is empty
s.push(node.data);
node.data = 0;
}
else
{
// Remove all top element of stack which is less than or
// equal to current node value
while (s.isEmpty() == false && s.peek() <= node.data)
{
// Remove top of stack
s.pop();
}
if (s.isEmpty() == true)
{
// After removing top element stack is empty
s.push(node.data);
// When no find largest node in a right side
node.data = 0;
}
else
{
int key = s.peek();
s.push(node.data);
// Set next largest value
node.data = key;
}
}
node = node.next;
}
// Reverse linked list
this.reverseElement();
}
}
public static void main(String[] args)
{
// Create a empty linked list
SingleLL sll = new SingleLL();
// Constructed linked list
// 4 → 2 → -7 → 3 → 9 → 1 → 4 → 10 → 8 →NULL
sll.addNode(4);
sll.addNode(2);
sll.addNode(-7);
sll.addNode(3);
sll.addNode(9);
sll.addNode(1);
sll.addNode(4);
sll.addNode(10);
sll.addNode(8);
System.out.print("\n Before Convert \n");
sll.display();
sll.nextLargest();
// After convert linked list
// 9 → 3 → 3 → 9 → 10 → 4 → 10 → 0 → 0 → NULL
System.out.print("\n After Convert \n");
sll.display();
}
}
Output
Before Convert
4 → 2 → -7 → 3 → 9 → 1 → 4 → 10 → 8 → NULL
After Convert
9 → 3 → 3 → 9 → 10 → 4 → 10 → 0 → 0 → NULL
// Include header file
#include <iostream>
using namespace std;
/*
C++ Program for
Next greater node in linked list
In O(n) Time
*/
// Define stack node
class StackNode
{
public: int element;
StackNode *next;
StackNode(int element, StackNode *top)
{
this->element = element;
this->next = top;
}
};
// Define a custom stack
class MyStack
{
public: StackNode *top;
int size;
MyStack()
{
//Set node values
this->top = NULL;
this->size = 0;
}
// Add node at the top of stack
void push(int element)
{
this->top = new StackNode(element, this->top);
this->size++;
}
bool isEmpty()
{
if (this->size > 0 && this->top != NULL)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
void pop()
{
if (this->size > 0 && this->top != NULL)
{
StackNode *temp = this->top;
// Change top element of stack
this->top = temp->next;
// remove previous top
temp = NULL;
this->size--;
}
}
// return top element of stack
int peek()
{
if (this->top == NULL)
{
return -1;
}
return this->top->element;
}
};
// Linked list node
class LinkNode
{
public: int data;
LinkNode *next;
LinkNode(int data)
{
this->data = data;
this->next = NULL;
}
};
class SingleLL
{
public: LinkNode *head;
LinkNode *tail;
SingleLL()
{
this->head = NULL;
this->tail = NULL;
}
//Add new Node at end of linked list
void addNode(int data)
{
LinkNode *node = new LinkNode(data);
if (this->head == NULL)
{
this->head = node;
}
else
{
// Append the node at last position
this->tail->next = node;
}
this->tail = node;
}
// Display linked list element
void display()
{
if (this->head == NULL)
{
cout << "\n Empty linked list\n";
return;
}
LinkNode *temp = this->head;
//iterating linked list elements
while (temp != NULL)
{
cout << " " << temp->data << " →";
// Visit to next node
temp = temp->next;
}
cout << " NULL\n";
}
// reversing the elements of linked list
void reverseElement()
{
LinkNode *node = this->head;
LinkNode *result = NULL;
LinkNode *temp = NULL;
while (node != NULL)
{
temp = node;
node = temp->next;
temp->next = result;
if (result == NULL)
{
// Set new tail node
this->tail = temp;
}
result = temp;
}
// Set new head
this->head = result;
}
// Change each node of linked from next largest node
void nextLargest()
{
if (this->head == NULL)
{
cout << "\n Empty Linked List ";
}
else
{
// First the reverse all elements of linked list
this->reverseElement();
LinkNode *node = this->head;
// Create an empty stack
MyStack s = MyStack();
// iterate linked list node
while (node != NULL)
{
if (s.isEmpty() == true)
{
// When stack is empty
s.push(node->data);
node->data = 0;
}
else
{
// Remove all top element of stack which is less than or
// equal to current node value
while (s.isEmpty() == false && s.peek() <= node->data)
{
// Remove top of stack
s.pop();
}
if (s.isEmpty() == true)
{
// After removing top element stack is empty
s.push(node->data);
// When no find largest node in a right side
node->data = 0;
}
else
{
int key = s.peek();
s.push(node->data);
// Set next largest value
node->data = key;
}
}
node = node->next;
}
// Reverse linked list
this->reverseElement();
}
}
};
int main()
{
// Create a empty linked list
SingleLL sll = SingleLL();
// Constructed linked list
// 4 → 2 → -7 → 3 → 9 → 1 → 4 → 10 → 8 →NULL
sll.addNode(4);
sll.addNode(2);
sll.addNode(-7);
sll.addNode(3);
sll.addNode(9);
sll.addNode(1);
sll.addNode(4);
sll.addNode(10);
sll.addNode(8);
cout << "\n Before Convert \n";
sll.display();
sll.nextLargest();
// After convert linked list
// 9 → 3 → 3 → 9 → 10 → 4 → 10 → 0 → 0 → NULL
cout << "\n After Convert \n";
sll.display();
return 0;
}
Output
Before Convert
4 → 2 → -7 → 3 → 9 → 1 → 4 → 10 → 8 → NULL
After Convert
9 → 3 → 3 → 9 → 10 → 4 → 10 → 0 → 0 → NULL
// Include namespace system
using System;
/*
C# Program for
Next greater node in linked list
In O(n) Time
*/
// Define stack node
public class StackNode
{
public int element;
public StackNode next;
public StackNode(int element, StackNode top)
{
this.element = element;
this.next = top;
}
}
// Define a custom stack
public class MyStack
{
public StackNode top;
public int size;
public MyStack()
{
//Set node values
this.top = null;
this.size = 0;
}
// Add node at the top of stack
public void push(int element)
{
this.top = new StackNode(element, this.top);
this.size++;
}
public Boolean isEmpty()
{
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
public void pop()
{
if (this.size > 0 && this.top != null)
{
StackNode temp = this.top;
// Change top element of stack
this.top = temp.next;
// remove previous top
temp = null;
this.size--;
}
}
// return top element of stack
public int peek()
{
if (this.top == null)
{
return -1;
}
return this.top.element;
}
}
// Linked list node
public class LinkNode
{
public int data;
public LinkNode next;
public LinkNode(int data)
{
this.data = data;
this.next = null;
}
}
public class SingleLL
{
public LinkNode head;
public LinkNode tail;
public SingleLL()
{
this.head = null;
this.tail = null;
}
//Add new Node at end of linked list
public void addNode(int data)
{
LinkNode node = new LinkNode(data);
if (this.head == null)
{
this.head = node;
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
// Display linked list element
public void display()
{
if (this.head == null)
{
Console.Write("\n Empty linked list\n");
return;
}
LinkNode temp = this.head;
//iterating linked list elements
while (temp != null)
{
Console.Write(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
Console.Write(" NULL\n");
}
// reversing the elements of linked list
public void reverseElement()
{
LinkNode node = this.head;
LinkNode result = null;
LinkNode temp = null;
while (node != null)
{
temp = node;
node = temp.next;
temp.next = result;
if (result == null)
{
// Set new tail node
this.tail = temp;
}
result = temp;
}
// Set new head
this.head = result;
}
// Change each node of linked from next largest node
public void nextLargest()
{
if (this.head == null)
{
Console.Write("\n Empty Linked List ");
}
else
{
// First the reverse all elements of linked list
this.reverseElement();
LinkNode node = this.head;
// Create an empty stack
MyStack s = new MyStack();
// iterate linked list node
while (node != null)
{
if (s.isEmpty() == true)
{
// When stack is empty
s.push(node.data);
node.data = 0;
}
else
{
// Remove all top element of stack which is less than or
// equal to current node value
while (s.isEmpty() == false && s.peek() <= node.data)
{
// Remove top of stack
s.pop();
}
if (s.isEmpty() == true)
{
// After removing top element stack is empty
s.push(node.data);
// When no find largest node in a right side
node.data = 0;
}
else
{
int key = s.peek();
s.push(node.data);
// Set next largest value
node.data = key;
}
}
node = node.next;
}
// Reverse linked list
this.reverseElement();
}
}
public static void Main(String[] args)
{
// Create a empty linked list
SingleLL sll = new SingleLL();
// Constructed linked list
// 4 → 2 → -7 → 3 → 9 → 1 → 4 → 10 → 8 →NULL
sll.addNode(4);
sll.addNode(2);
sll.addNode(-7);
sll.addNode(3);
sll.addNode(9);
sll.addNode(1);
sll.addNode(4);
sll.addNode(10);
sll.addNode(8);
Console.Write("\n Before Convert \n");
sll.display();
sll.nextLargest();
// After convert linked list
// 9 → 3 → 3 → 9 → 10 → 4 → 10 → 0 → 0 → NULL
Console.Write("\n After Convert \n");
sll.display();
}
}
Output
Before Convert
4 → 2 → -7 → 3 → 9 → 1 → 4 → 10 → 8 → NULL
After Convert
9 → 3 → 3 → 9 → 10 → 4 → 10 → 0 → 0 → NULL
<?php
/*
Php Program for
Next greater node in linked list
In O(n) Time
*/
// Define stack node
class StackNode
{
public $element;
public $next;
function __construct($element, $top)
{
$this->element = $element;
$this->next = $top;
}
}
// Define a custom stack
class MyStack
{
public $top;
public $size;
function __construct()
{
//Set node values
$this->top = null;
$this->size = 0;
}
// Add node at the top of stack
public function push($element)
{
$this->top = new StackNode($element, $this->top);
$this->size++;
}
public function isEmpty()
{
if ($this->size > 0 && $this->top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
public function pop()
{
if ($this->size > 0 && $this->top != null)
{
$temp = $this->top;
// Change top element of stack
$this->top = $temp->next;
// remove previous top
$temp = null;
$this->size--;
}
}
// return top element of stack
public function peek()
{
if ($this->top == null)
{
return -1;
}
return $this->top->element;
}
}
// Linked list node
class LinkNode
{
public $data;
public $next;
function __construct($data)
{
$this->data = $data;
$this->next = null;
}
}
class SingleLL
{
public $head;
public $tail;
function __construct()
{
$this->head = null;
$this->tail = null;
}
//Add new Node at end of linked list
public function addNode($data)
{
$node = new LinkNode($data);
if ($this->head == null)
{
$this->head = $node;
}
else
{
// Append the node at last position
$this->tail->next = $node;
}
$this->tail = $node;
}
// Display linked list element
public function display()
{
if ($this->head == null)
{
echo "\n Empty linked list\n";
return;
}
$temp = $this->head;
//iterating linked list elements
while ($temp != null)
{
echo " ". $temp->data ." →";
// Visit to next node
$temp = $temp->next;
}
echo " NULL\n";
}
// reversing the elements of linked list
public function reverseElement()
{
$node = $this->head;
$result = null;
$temp = null;
while ($node != null)
{
$temp = $node;
$node = $temp->next;
$temp->next = $result;
if ($result == null)
{
// Set new tail node
$this->tail = $temp;
}
$result = $temp;
}
// Set new head
$this->head = $result;
}
// Change each node of linked from next largest node
public function nextLargest()
{
if ($this->head == null)
{
echo "\n Empty Linked List ";
}
else
{
// First the reverse all elements of linked list
$this->reverseElement();
$node = $this->head;
// Create an empty stack
$s = new MyStack();
// iterate linked list node
while ($node != null)
{
if ($s->isEmpty() == true)
{
// When stack is empty
$s->push($node->data);
$node->data = 0;
}
else
{
// Remove all top element of stack which is less than or
// equal to current node value
while ($s->isEmpty() == false && $s->peek() <= $node->data)
{
// Remove top of stack
$s->pop();
}
if ($s->isEmpty() == true)
{
// After removing top element stack is empty
$s->push($node->data);
// When no find largest node in a right side
$node->data = 0;
}
else
{
$key = $s->peek();
$s->push($node->data);
// Set next largest value
$node->data = $key;
}
}
$node = $node->next;
}
// Reverse linked list
$this->reverseElement();
}
}
}
function main()
{
// Create a empty linked list
$sll = new SingleLL();
// Constructed linked list
// 4 → 2 → -7 → 3 → 9 → 1 → 4 → 10 → 8 →NULL
$sll->addNode(4);
$sll->addNode(2);
$sll->addNode(-7);
$sll->addNode(3);
$sll->addNode(9);
$sll->addNode(1);
$sll->addNode(4);
$sll->addNode(10);
$sll->addNode(8);
echo "\n Before Convert \n";
$sll->display();
$sll->nextLargest();
// After convert linked list
// 9 → 3 → 3 → 9 → 10 → 4 → 10 → 0 → 0 → NULL
echo "\n After Convert \n";
$sll->display();
}
main();
Output
Before Convert
4 → 2 → -7 → 3 → 9 → 1 → 4 → 10 → 8 → NULL
After Convert
9 → 3 → 3 → 9 → 10 → 4 → 10 → 0 → 0 → NULL
/*
Node Js Program for
Next greater node in linked list
In O(n) Time
*/
// Define stack node
class StackNode
{
constructor(element, top)
{
this.element = element;
this.next = top;
}
}
// Define a custom stack
class MyStack
{
constructor()
{
//Set node values
this.top = null;
this.size = 0;
}
// Add node at the top of stack
push(element)
{
this.top = new StackNode(element, this.top);
this.size++;
}
isEmpty()
{
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
pop()
{
if (this.size > 0 && this.top != null)
{
var temp = this.top;
// Change top element of stack
this.top = temp.next;
// remove previous top
temp = null;
this.size--;
}
}
// return top element of stack
peek()
{
if (this.top == null)
{
return -1;
}
return this.top.element;
}
}
// Linked list node
class LinkNode
{
constructor(data)
{
this.data = data;
this.next = null;
}
}
class SingleLL
{
constructor()
{
this.head = null;
this.tail = null;
}
//Add new Node at end of linked list
addNode(data)
{
var node = new LinkNode(data);
if (this.head == null)
{
this.head = node;
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
// Display linked list element
display()
{
if (this.head == null)
{
process.stdout.write("\n Empty linked list\n");
return;
}
var temp = this.head;
//iterating linked list elements
while (temp != null)
{
process.stdout.write(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
process.stdout.write(" NULL\n");
}
// reversing the elements of linked list
reverseElement()
{
var node = this.head;
var result = null;
var temp = null;
while (node != null)
{
temp = node;
node = temp.next;
temp.next = result;
if (result == null)
{
// Set new tail node
this.tail = temp;
}
result = temp;
}
// Set new head
this.head = result;
}
// Change each node of linked from next largest node
nextLargest()
{
if (this.head == null)
{
process.stdout.write("\n Empty Linked List ");
}
else
{
// First the reverse all elements of linked list
this.reverseElement();
var node = this.head;
// Create an empty stack
var s = new MyStack();
// iterate linked list node
while (node != null)
{
if (s.isEmpty() == true)
{
// When stack is empty
s.push(node.data);
node.data = 0;
}
else
{
// Remove all top element of stack which is less than or
// equal to current node value
while (s.isEmpty() == false && s.peek() <= node.data)
{
// Remove top of stack
s.pop();
}
if (s.isEmpty() == true)
{
// After removing top element stack is empty
s.push(node.data);
// When no find largest node in a right side
node.data = 0;
}
else
{
var key = s.peek();
s.push(node.data);
// Set next largest value
node.data = key;
}
}
node = node.next;
}
// Reverse linked list
this.reverseElement();
}
}
}
function main()
{
// Create a empty linked list
var sll = new SingleLL();
// Constructed linked list
// 4 → 2 → -7 → 3 → 9 → 1 → 4 → 10 → 8 →NULL
sll.addNode(4);
sll.addNode(2);
sll.addNode(-7);
sll.addNode(3);
sll.addNode(9);
sll.addNode(1);
sll.addNode(4);
sll.addNode(10);
sll.addNode(8);
process.stdout.write("\n Before Convert \n");
sll.display();
sll.nextLargest();
// After convert linked list
// 9 → 3 → 3 → 9 → 10 → 4 → 10 → 0 → 0 → NULL
process.stdout.write("\n After Convert \n");
sll.display();
}
main();
Output
Before Convert
4 → 2 → -7 → 3 → 9 → 1 → 4 → 10 → 8 → NULL
After Convert
9 → 3 → 3 → 9 → 10 → 4 → 10 → 0 → 0 → NULL
# Python 3 Program for
# Next greater node in linked list
# In O(n) Time
# Define stack node
class StackNode :
def __init__(self, element, top) :
self.element = element
self.next = top
# Define a custom stack
class MyStack :
def __init__(self) :
# Set node values
self.top = None
self.size = 0
# Add node at the top of stack
def push(self, element) :
self.top = StackNode(element, self.top)
self.size += 1
def isEmpty(self) :
if (self.size > 0 and self.top != None) :
return False
else :
return True
# Remove top element of stack
def pop(self) :
if (self.size > 0 and self.top != None) :
temp = self.top
# Change top element of stack
self.top = temp.next
# remove previous top
temp = None
self.size -= 1
# return top element of stack
def peek(self) :
if (self.top == None) :
return -1
return self.top.element
# Linked list node
class LinkNode :
def __init__(self, data) :
self.data = data
self.next = None
class SingleLL :
def __init__(self) :
self.head = None
self.tail = None
# Add new Node at end of linked list
def addNode(self, data) :
node = LinkNode(data)
if (self.head == None) :
self.head = node
else :
# Append the node at last position
self.tail.next = node
self.tail = node
# Display linked list element
def display(self) :
if (self.head == None) :
print("\n Empty linked list")
return
temp = self.head
# iterating linked list elements
while (temp != None) :
print("", temp.data ,"→", end = "")
# Visit to next node
temp = temp.next
print(" NULL")
# reversing the elements of linked list
def reverseElement(self) :
node = self.head
result = None
temp = None
while (node != None) :
temp = node
node = temp.next
temp.next = result
if (result == None) :
# Set new tail node
self.tail = temp
result = temp
# Set new head
self.head = result
# Change each node of linked from next largest node
def nextLargest(self) :
if (self.head == None) :
print("\n Empty Linked List ", end = "")
else :
# First the reverse all elements of linked list
self.reverseElement()
node = self.head
# Create an empty stack
s = MyStack()
# iterate linked list node
while (node != None) :
if (s.isEmpty() == True) :
# When stack is empty
s.push(node.data)
node.data = 0
else :
# Remove all top element of stack which is less than or
# equal to current node value
while (s.isEmpty() == False and s.peek() <= node.data) :
# Remove top of stack
s.pop()
if (s.isEmpty() == True) :
# After removing top element stack is empty
s.push(node.data)
# When no find largest node in a right side
node.data = 0
else :
key = s.peek()
s.push(node.data)
# Set next largest value
node.data = key
node = node.next
# Reverse linked list
self.reverseElement()
def main() :
# Create a empty linked list
sll = SingleLL()
# Constructed linked list
# 4 → 2 → -7 → 3 → 9 → 1 → 4 → 10 → 8 →NULL
sll.addNode(4)
sll.addNode(2)
sll.addNode(-7)
sll.addNode(3)
sll.addNode(9)
sll.addNode(1)
sll.addNode(4)
sll.addNode(10)
sll.addNode(8)
print("\n Before Convert ")
sll.display()
sll.nextLargest()
# After convert linked list
# 9 → 3 → 3 → 9 → 10 → 4 → 10 → 0 → 0 → NULL
print("\n After Convert ")
sll.display()
if __name__ == "__main__": main()
Output
Before Convert
4 → 2 → -7 → 3 → 9 → 1 → 4 → 10 → 8 → NULL
After Convert
9 → 3 → 3 → 9 → 10 → 4 → 10 → 0 → 0 → NULL
# Ruby Program for
# Next greater node in linked list
# In O(n) Time
# Define stack node
class StackNode
# Define the accessor and reader of class StackNode
attr_reader :element, :next
attr_accessor :element, :next
def initialize(element, top)
self.element = element
self.next = top
end
end
# Define a custom stack
class MyStack
# Define the accessor and reader of class MyStack
attr_reader :top, :size
attr_accessor :top, :size
def initialize()
# Set node values
self.top = nil
self.size = 0
end
# Add node at the top of stack
def push(element)
self.top = StackNode.new(element, self.top)
self.size += 1
end
def isEmpty()
if (self.size > 0 && self.top != nil)
return false
else
return true
end
end
# Remove top element of stack
def pop()
if (self.size > 0 && self.top != nil)
temp = self.top
# Change top element of stack
self.top = temp.next
# remove previous top
temp = nil
self.size -= 1
end
end
# return top element of stack
def peek()
if (self.top == nil)
return -1
end
return self.top.element
end
end
# Linked list node
class LinkNode
# Define the accessor and reader of class LinkNode
attr_reader :data, :next
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
attr_reader :head, :tail
attr_accessor :head, :tail
def initialize()
self.head = nil
self.tail = nil
end
# Add new Node at end of linked list
def addNode(data)
node = LinkNode.new(data)
if (self.head == nil)
self.head = node
else
# Append the node at last position
self.tail.next = node
end
self.tail = node
end
# Display linked list element
def display()
if (self.head == nil)
print("\n Empty linked list\n")
return
end
temp = self.head
# iterating linked list elements
while (temp != nil)
print(" ", temp.data ," →")
# Visit to next node
temp = temp.next
end
print(" NULL\n")
end
# reversing the elements of linked list
def reverseElement()
node = self.head
result = nil
temp = nil
while (node != nil)
temp = node
node = temp.next
temp.next = result
if (result == nil)
# Set new tail node
self.tail = temp
end
result = temp
end
# Set new head
self.head = result
end
# Change each node of linked from next largest node
def nextLargest()
if (self.head == nil)
print("\n Empty Linked List ")
else
# First the reverse all elements of linked list
self.reverseElement()
node = self.head
# Create an empty stack
s = MyStack.new()
# iterate linked list node
while (node != nil)
if (s.isEmpty() == true)
# When stack is empty
s.push(node.data)
node.data = 0
else
# Remove all top element of stack which is less than or
# equal to current node value
while (s.isEmpty() == false && s.peek() <= node.data)
# Remove top of stack
s.pop()
end
if (s.isEmpty() == true)
# After removing top element stack is empty
s.push(node.data)
# When no find largest node in a right side
node.data = 0
else
key = s.peek()
s.push(node.data)
# Set next largest value
node.data = key
end
end
node = node.next
end
# Reverse linked list
self.reverseElement()
end
end
end
def main()
# Create a empty linked list
sll = SingleLL.new()
# Constructed linked list
# 4 → 2 → -7 → 3 → 9 → 1 → 4 → 10 → 8 →NULL
sll.addNode(4)
sll.addNode(2)
sll.addNode(-7)
sll.addNode(3)
sll.addNode(9)
sll.addNode(1)
sll.addNode(4)
sll.addNode(10)
sll.addNode(8)
print("\n Before Convert \n")
sll.display()
sll.nextLargest()
# After convert linked list
# 9 → 3 → 3 → 9 → 10 → 4 → 10 → 0 → 0 → NULL
print("\n After Convert \n")
sll.display()
end
main()
Output
Before Convert
4 → 2 → -7 → 3 → 9 → 1 → 4 → 10 → 8 → NULL
After Convert
9 → 3 → 3 → 9 → 10 → 4 → 10 → 0 → 0 → NULL
/*
Scala Program for
Next greater node in linked list
In O(n) Time
*/
// Define stack node
class StackNode(var element: Int , var next: StackNode);
// Define a custom stack
class MyStack(var top: StackNode , var size: Int)
{
def this()
{
this(null, 0);
}
// Add node at the top of stack
def push(element: Int): Unit = {
this.top = new StackNode(element, this.top);
this.size += 1;
}
def isEmpty(): Boolean = {
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
def pop(): Unit = {
if (this.size > 0 && this.top != null)
{
var temp: StackNode = this.top;
// Change top element of stack
this.top = temp.next;
// remove previous top
temp = null;
this.size -= 1;
}
}
// return top element of stack
def peek(): Int = {
if (this.top == null)
{
return -1;
}
return this.top.element;
}
}
// Linked list node
class LinkNode(var data: Int , var next: LinkNode)
{
def this(data: Int)
{
this(data, null);
}
}
class SingleLL(var head: LinkNode , var tail: LinkNode)
{
def this()
{
this(null, null);
}
//Add new Node at end of linked list
def addNode(data: Int): Unit = {
var node: LinkNode = new LinkNode(data);
if (this.head == null)
{
this.head = node;
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
// Display linked list element
def display(): Unit = {
if (this.head == null)
{
print("\n Empty linked list\n");
return;
}
var temp: LinkNode = this.head;
//iterating linked list elements
while (temp != null)
{
print(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
print(" NULL\n");
}
// reversing the elements of linked list
def reverseElement(): Unit = {
var node: LinkNode = this.head;
var result: LinkNode = null;
var temp: LinkNode = null;
while (node != null)
{
temp = node;
node = temp.next;
temp.next = result;
if (result == null)
{
// Set new tail node
this.tail = temp;
}
result = temp;
}
// Set new head
this.head = result;
}
// Change each node of linked from next largest node
def nextLargest(): Unit = {
if (this.head == null)
{
print("\n Empty Linked List ");
}
else
{
// First the reverse all elements of linked list
this.reverseElement();
var node: LinkNode = this.head;
// Create an empty stack
var s: MyStack = new MyStack();
// iterate linked list node
while (node != null)
{
if (s.isEmpty() == true)
{
// When stack is empty
s.push(node.data);
node.data = 0;
}
else
{
// Remove all top element of stack which is less than or
// equal to current node value
while (s.isEmpty() == false && s.peek() <= node.data)
{
// Remove top of stack
s.pop();
}
if (s.isEmpty() == true)
{
// After removing top element stack is empty
s.push(node.data);
// When no find largest node in a right side
node.data = 0;
}
else
{
var key: Int = s.peek();
s.push(node.data);
// Set next largest value
node.data = key;
}
}
node = node.next;
}
// Reverse linked list
this.reverseElement();
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
// Create a empty linked list
var sll: SingleLL = new SingleLL();
// Constructed linked list
// 4 → 2 → -7 → 3 → 9 → 1 → 4 → 10 → 8 →NULL
sll.addNode(4);
sll.addNode(2);
sll.addNode(-7);
sll.addNode(3);
sll.addNode(9);
sll.addNode(1);
sll.addNode(4);
sll.addNode(10);
sll.addNode(8);
print("\n Before Convert \n");
sll.display();
sll.nextLargest();
// After convert linked list
// 9 → 3 → 3 → 9 → 10 → 4 → 10 → 0 → 0 → NULL
print("\n After Convert \n");
sll.display();
}
}
Output
Before Convert
4 → 2 → -7 → 3 → 9 → 1 → 4 → 10 → 8 → NULL
After Convert
9 → 3 → 3 → 9 → 10 → 4 → 10 → 0 → 0 → NULL
/*
Swift 4 Program for
Next greater node in linked list
In O(n) Time
*/
// Define stack node
class StackNode
{
var element: Int;
var next: StackNode? ;
init(_ element: Int, _ top: StackNode? )
{
self.element = element;
self.next = top;
}
}
// Define a custom stack
class MyStack
{
var top: StackNode? ;
var size: Int;
init()
{
//Set node values
self.top = nil;
self.size = 0;
}
// Add node at the top of stack
func push(_ element: Int)
{
self.top = StackNode(element, self.top);
self.size += 1;
}
func isEmpty()->Bool
{
if (self.size > 0 && self.top != nil)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
func pop()
{
if (self.size > 0 && self.top != nil)
{
var temp: StackNode? = self.top;
// Change top element of stack
self.top = temp!.next;
// remove previous top
temp = nil;
self.size -= 1;
}
}
// return top element of stack
func peek()->Int
{
if (self.top == nil)
{
return -1;
}
return self.top!.element;
}
}
// Linked list node
class LinkNode
{
var data: Int;
var next: LinkNode? ;
init(_ data: Int)
{
self.data = data;
self.next = nil;
}
}
class SingleLL
{
var head: LinkNode? ;
var tail: LinkNode? ;
init()
{
self.head = nil;
self.tail = nil;
}
//Add new Node at end of linked list
func addNode(_ data: Int)
{
let node: LinkNode? = LinkNode(data);
if (self.head == nil)
{
self.head = node;
}
else
{
// Append the node at last position
self.tail!.next = node;
}
self.tail = node;
}
// Display linked list element
func display()
{
if (self.head == nil)
{
print("\n Empty linked list");
return;
}
var temp: LinkNode? = self.head;
//iterating linked list elements
while (temp != nil)
{
print("", temp!.data ,"→", terminator: "");
// Visit to next node
temp = temp!.next;
}
print(" NULL");
}
// reversing the elements of linked list
func reverseElement()
{
var node: LinkNode? = self.head;
var result: LinkNode? = nil;
var temp: LinkNode? = nil;
while (node != nil)
{
temp = node;
node = temp!.next;
temp!.next = result;
if (result == nil)
{
// Set new tail node
self.tail = temp;
}
result = temp;
}
// Set new head
self.head = result;
}
// Change each node of linked from next largest node
func nextLargest()
{
if (self.head == nil)
{
print("\n Empty Linked List ", terminator: "");
}
else
{
// First the reverse all elements of linked list
self.reverseElement();
var node: LinkNode? = self.head;
// Create an empty stack
let s: MyStack = MyStack();
// iterate linked list node
while (node != nil)
{
if (s.isEmpty() == true)
{
// When stack is empty
s.push(node!.data);
node!.data = 0;
}
else
{
// Remove all top element of stack which is less than or
// equal to current node value
while (s.isEmpty() == false && s.peek() <= node!.data)
{
// Remove top of stack
s.pop();
}
if (s.isEmpty() == true)
{
// After removing top element stack is empty
s.push(node!.data);
// When no find largest node in a right side
node!.data = 0;
}
else
{
let key: Int = s.peek();
s.push(node!.data);
// Set next largest value
node!.data = key;
}
}
node = node!.next;
}
// Reverse linked list
self.reverseElement();
}
}
}
func main()
{
// Create a empty linked list
let sll: SingleLL = SingleLL();
// Constructed linked list
// 4 → 2 → -7 → 3 → 9 → 1 → 4 → 10 → 8 →NULL
sll.addNode(4);
sll.addNode(2);
sll.addNode(-7);
sll.addNode(3);
sll.addNode(9);
sll.addNode(1);
sll.addNode(4);
sll.addNode(10);
sll.addNode(8);
print("\n Before Convert ");
sll.display();
sll.nextLargest();
// After convert linked list
// 9 → 3 → 3 → 9 → 10 → 4 → 10 → 0 → 0 → NULL
print("\n After Convert ");
sll.display();
}
main();
Output
Before Convert
4 → 2 → -7 → 3 → 9 → 1 → 4 → 10 → 8 → NULL
After Convert
9 → 3 → 3 → 9 → 10 → 4 → 10 → 0 → 0 → NULL
/*
Kotlin Program for
Next greater node in linked list
In O(n) Time
*/
// Define stack node
class StackNode
{
var element: Int;
var next: StackNode ? ;
constructor(element: Int, top: StackNode ? )
{
this.element = element;
this.next = top;
}
}
// Define a custom stack
class MyStack
{
var top: StackNode ? ;
var size: Int;
constructor()
{
//Set node values
this.top = null;
this.size = 0;
}
// Add node at the top of stack
fun push(element: Int): Unit
{
this.top = StackNode(element, this.top);
this.size += 1;
}
fun isEmpty(): Boolean
{
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
fun pop(): Unit
{
if (this.size > 0 && this.top != null)
{
var temp: StackNode ? = this.top;
// Change top element of stack
this.top = temp?.next;
this.size -= 1;
}
}
// return top element of stack
fun peek(): Int
{
if (this.top == null)
{
return -1;
}
return this.top!!.element;
}
}
// Linked list node
class LinkNode
{
var data: Int;
var next: LinkNode ? ;
constructor(data: Int)
{
this.data = data;
this.next = null;
}
}
class SingleLL
{
var head: LinkNode ? ;
var tail: LinkNode ? ;
constructor()
{
this.head = null;
this.tail = null;
}
//Add new Node at end of linked list
fun addNode(data: Int): Unit
{
var node: LinkNode ? = LinkNode(data);
if (this.head == null)
{
this.head = node;
}
else
{
// Append the node at last position
this.tail?.next = node;
}
this.tail = node;
}
// Display linked list element
fun display(): Unit
{
if (this.head == null)
{
print("\n Empty linked list\n");
return;
}
var temp: LinkNode ? = this.head;
//iterating linked list elements
while (temp != null)
{
print(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
print(" NULL\n");
}
// reversing the elements of linked list
fun reverseElement(): Unit
{
var node: LinkNode ? = this.head;
var result: LinkNode ? = null ;
var temp: LinkNode ? ;
while (node != null)
{
temp = node;
node = temp.next;
temp.next = result;
if (result == null)
{
// Set new tail node
this.tail = temp;
}
result = temp;
}
// Set new head
this.head = result;
}
// Change each node of linked from next largest node
fun nextLargest(): Unit
{
if (this.head == null)
{
print("\n Empty Linked List ");
}
else
{
// First the reverse all elements of linked list
this.reverseElement();
var node: LinkNode ? = this.head;
// Create an empty stack
var s: MyStack = MyStack();
// iterate linked list node
while (node != null)
{
if (s.isEmpty() == true)
{
// When stack is empty
s.push(node.data);
node.data = 0;
}
else
{
// Remove all top element of stack which is less than or
// equal to current node value
while (s.isEmpty() == false && s.peek() <= node.data)
{
// Remove top of stack
s.pop();
}
if (s.isEmpty() == true)
{
// After removing top element stack is empty
s.push(node.data);
// When no find largest node in a right side
node.data = 0;
}
else
{
var key: Int = s.peek();
s.push(node.data);
// Set next largest value
node.data = key;
}
}
node = node.next;
}
// Reverse linked list
this.reverseElement();
}
}
}
fun main(args: Array <String> ): Unit
{
// Create a empty linked list
var sll: SingleLL = SingleLL();
// Constructed linked list
// 4 → 2 → -7 → 3 → 9 → 1 → 4 → 10 → 8 →NULL
sll.addNode(4);
sll.addNode(2);
sll.addNode(-7);
sll.addNode(3);
sll.addNode(9);
sll.addNode(1);
sll.addNode(4);
sll.addNode(10);
sll.addNode(8);
print("\n Before Convert \n");
sll.display();
sll.nextLargest();
// After convert linked list
// 9 → 3 → 3 → 9 → 10 → 4 → 10 → 0 → 0 → NULL
print("\n After Convert \n");
sll.display();
}
Output
Before Convert
4 → 2 → -7 → 3 → 9 → 1 → 4 → 10 → 8 → NULL
After Convert
9 → 3 → 3 → 9 → 10 → 4 → 10 → 0 → 0 → NULL
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.
New Comment