Find a peak element in linked list
Given a linked list which is containing elements of integer data value. Our goal is to find a element whose value is greater than its own left and right side nodes. For example.
Example 1 ---------- Linked List : 1 → 5 → 6 → 2 → NULL ↓ P1 [ P1 is peak node because (5 > 1), 5 is greater than of left side node [1] . And (5>2), 5 is greater than of right side node [2]. ] Output : 5 Example 2 ---------- Linked List : 4 → 6 → 5 → 10 → 3 → NULL ↓ ↓ ↓ P1 P2 P3 [ P1 and P2 is peak node because (6 > 4), 6 is greater than of left side node [4] . And (6>3), 5 is greater than of right side node [3]. or (5 > 4), 5 is greater than of left side node [4] . And (5>3), 5 is greater than of right side node [3]. or (10 > 5), 10 is greater than of previous node [5] . And (10>3), 10 is greater than of next node [3]. ] Output : 10 [Get first one] Example 3 ---------- Linked List : 1 → 2 → 4 → NULL Output : None [Because no peak node in this linked list] Example 4 --------- Linked List : 1 → 3 → 2 → 4 → 5 → 4 → NULL ↓ ↓ P1 P2 [ P1 and P2 is peak node Because (3 > 1), 3 is greater than of previous node [1] . And (3>2), 3 is greater than of next node [2]. Similar 5 is greater than of left side node [1,3,2,4 (note we need one smallest)] 5 is greater than of right side [4]. ] Output : 3 [Get first one]
Here given code implementation process.
// C Program
// Find a peak element in linked list
#include <stdio.h>
//For malloc function
#include <stdlib.h>
//Linked List Node
struct Node
{
int data;
struct Node *next;
};
//Create a node of linked list
struct Node *create_node(int data)
{
//Create dynamic node
struct Node *node = (struct Node *) malloc(sizeof(struct Node));
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 insert(struct Node **head, int data)
{
struct Node *node = create_node(data);
if ( *head == NULL)
{
*head = node;
}
else
{
struct Node *temp = *head;
//Find last node
while (temp->next != NULL)
{
temp = temp->next;
}
//Add node at last possition
temp->next = node;
}
}
//Display linked list element
void display(struct Node *head)
{
if (head == NULL)
{
printf("\nEmpty linked list\n");
return;
}
struct Node *temp = head;
printf("\n Linked List : ");
//iterating linked list elements
while (temp != NULL)
{
if(temp != head)
{
printf(" →");
}
printf(" %d", temp->data);
//visit to next node
temp = temp->next;
}
printf(" → NULL");
}
//Check that left side smaller element exist or not
int is_left_side_smaller(struct Node*start,struct Node*last)
{
while(start != NULL && start != last)
{
if(start->data < last->data)
{
return 1;
}
//visit to next node
start = start->next;
}
return 0;
}
//Check that right side smaller element exist or not
int is_right_side_smaller(struct Node*start)
{
struct Node*temp = start->next;
while(temp != NULL)
{
if(temp->data < start->data)
{
return 1;
}
temp = temp->next;
}
return 0;
}
//Find first peak node in given linked list
void peak_node(struct Node *head)
{
//Display linked list elements
display(head);
struct Node *result = NULL;
if(head!=NULL && head->next!=NULL)
{
//Define some auxiliary variable
struct Node *current = head->next;
//iterating linked list elements
while (current != NULL && result == NULL && current->next != NULL)
{
if(is_left_side_smaller(head,current)
&& is_right_side_smaller(current))
{
result = current;
}
//visit to next node
current = current->next;
}
}
if (result == NULL)
{
printf("\n Peak node : None\n");
}
else
{
printf("\n Peak node : %d\n", result->data);
}
}
int main()
{
//Define few empty linked list
struct Node *list1 = NULL;
struct Node *list2 = NULL;
struct Node *list3 = NULL;
//Add node in first linked list
// 1 → 5 → 6 → 2 → NULL
insert( &list1, 1);
insert( &list1, 5);
insert( &list1, 6);
insert( &list1, 2);
peak_node(list1);
//Add node in second linked list
// 4 → 6 → 5 → 10 → 3 → NULL
insert( &list2, 4);
insert( &list2, 6);
insert( &list2, 5);
insert( &list2, 10);
insert( &list2, 3);
peak_node(list2);
//Add node in third linked list
// 1 → 2 → 4 → NULL
insert( &list3, 1);
insert( &list3, 2);
insert( &list3, 4);
peak_node(list3);
return 0;
}
Output
Linked List : 1 → 5 → 6 → 2 → NULL
Peak node : 5
Linked List : 4 → 6 → 5 → 10 → 3 → NULL
Peak node : 6
Linked List : 1 → 2 → 4 → NULL
Peak node : None
// Java Program
// Find a peak element in linked list
//Node of LinkedList
class Node
{
public int data;
public Node next;
public Node(int data)
{
//Set node value
this.data = data;
this.next = null;
}
}
class MyLinkedList
{
public Node head;
public Node tail;
//Class constructor
public MyLinkedList()
{
this.head = null;
this.tail = null;
}
//insert node at last of linke list
public void insert(int data)
{
//Create a node
Node node = new Node(data);
if (this.head == null)
{
//When linked list empty add first node
this.head = node;
this.tail = node;
}
else
{
//Add new node at end of linked list
this.tail.next = node;
this.tail = node;
}
}
//Display linked list element
public void display()
{
if (this.head == null)
{
System.out.print("\nEmpty linked list\n");
return;
}
Node temp = this.head;
System.out.print("\n Linked List : ");
//iterating linked list elements
while (temp != null)
{
if (temp != this.head)
{
System.out.print(" →");
}
System.out.print(" " + temp.data);
//visit to next node
temp = temp.next;
}
System.out.print(" → NULL");
}
//Check that left side smaller element exist or not
public boolean is_left_side_smaller(Node start, Node last)
{
while (start != null && start != last)
{
if (start.data < last.data)
{
return true;
}
start = start.next;
}
return false;
}
//Check that right side smaller element exist or not
public boolean is_right_side_smaller(Node start)
{
Node temp = start.next;
while (temp != null)
{
if (temp.data < start.data)
{
return true;
}
temp = temp.next;
}
return false;
}
//Find first peak node in given linked list
public void peak_node()
{
//Display linked list elements
this.display();
Node result = null;
if (this.head != null && this.head.next != null)
{
//Define some auxiliary variable
Node current = this.head.next;
//iterating linked list elements
while (current != null && result == null && current.next != null)
{
if (is_left_side_smaller(this.head, current) && is_right_side_smaller(current))
{
result = current;
}
//visit to next node
current = current.next;
}
}
if (result == null)
{
System.out.print("\n Peak node : None\n");
}
else
{
System.out.print("\n Peak node : " + result.data + "\n");
}
}
public static void main(String[] args)
{
MyLinkedList list1 = new MyLinkedList();
MyLinkedList list2 = new MyLinkedList();
MyLinkedList list3 = new MyLinkedList();
//Add node in first linked list
// 1 → 5 → 6 → 2 → NULL
list1.insert(1);
list1.insert(5);
list1.insert(6);
list1.insert(2);
list1.peak_node();
//Add node in second linked list
// 4 → 6 → 5 → 10 → 3 → NULL
list2.insert(4);
list2.insert(6);
list2.insert(5);
list2.insert(10);
list2.insert(3);
list2.peak_node();
//Add node in third linked list
// 1 → 2 → 4 → NULL
list3.insert(1);
list3.insert(2);
list3.insert(4);
list3.peak_node();
}
}
Output
Linked List : 1 → 5 → 6 → 2 → NULL
Peak node : 5
Linked List : 4 → 6 → 5 → 10 → 3 → NULL
Peak node : 6
Linked List : 1 → 2 → 4 → NULL
Peak node : None
//Include header file
#include <iostream>
using namespace std;
// C++ Program
// Find a peak element in linked list
//Node of LinkedList
class Node
{
public: int data;
Node *next;
Node(int data)
{
//Set node value
this->data = data;
this->next = NULL;
}
};
class MyLinkedList
{
public: Node *head;
Node *tail;
//Class constructor
MyLinkedList()
{
this->head = NULL;
this->tail = NULL;
}
//insert node at last of linke list
void insert(int data)
{
//Create a node
Node *node = new Node(data);
if (this->head == NULL)
{
//When linked list empty add first node
this->head = node;
this->tail = node;
}
else
{
//Add new node at end of linked list
this->tail->next = node;
this->tail = node;
}
}
//Display linked list element
void display()
{
if (this->head == NULL)
{
cout << "\nEmpty linked list\n";
return;
}
Node *temp = this->head;
cout << "\n Linked List : ";
//iterating linked list elements
while (temp != NULL)
{
if (temp != this->head)
{
cout << " →";
}
cout << " " << temp->data;
//visit to next node
temp = temp->next;
}
cout << " → NULL";
}
//Check that left side smaller element exist or not
bool is_left_side_smaller(Node *start, Node *last)
{
while (start != NULL && start != last)
{
if (start->data < last->data)
{
return true;
}
start = start->next;
}
return false;
}
//Check that right side smaller element exist or not
bool is_right_side_smaller(Node *start)
{
Node *temp = start->next;
while (temp != NULL)
{
if (temp->data < start->data)
{
return true;
}
temp = temp->next;
}
return false;
}
//Find first peak node in given linked list
void peak_node()
{
//Display linked list elements
this->display();
Node *result = NULL;
if (this->head != NULL && this->head->next != NULL)
{
//Define some auxiliary variable
Node *current = this->head->next;
//iterating linked list elements
while (current != NULL && result == NULL && current->next != NULL)
{
if (this->is_left_side_smaller(this->head, current) && this->is_right_side_smaller(current))
{
result = current;
}
//visit to next node
current = current->next;
}
}
if (result == NULL)
{
cout << "\n Peak node : None\n";
}
else
{
cout << "\n Peak node : " << result->data << "\n";
}
}
};
int main()
{
MyLinkedList list1 = MyLinkedList();
MyLinkedList list2 = MyLinkedList();
MyLinkedList list3 = MyLinkedList();
//Add node in first linked list
// 1 → 5 → 6 → 2 → NULL
list1.insert(1);
list1.insert(5);
list1.insert(6);
list1.insert(2);
list1.peak_node();
//Add node in second linked list
// 4 → 6 → 5 → 10 → 3 → NULL
list2.insert(4);
list2.insert(6);
list2.insert(5);
list2.insert(10);
list2.insert(3);
list2.peak_node();
//Add node in third linked list
// 1 → 2 → 4 → NULL
list3.insert(1);
list3.insert(2);
list3.insert(4);
list3.peak_node();
return 0;
}
Output
Linked List : 1 → 5 → 6 → 2 → NULL
Peak node : 5
Linked List : 4 → 6 → 5 → 10 → 3 → NULL
Peak node : 6
Linked List : 1 → 2 → 4 → NULL
Peak node : None
//Include namespace system
using System;
// C# Program
// Find a peak element in linked list
//Node of LinkedList
class Node
{
public int data;
public Node next;
public Node(int data)
{
//Set node value
this.data = data;
this.next = null;
}
}
class MyLinkedList
{
public Node head;
public Node tail;
//Class constructor
public MyLinkedList()
{
this.head = null;
this.tail = null;
}
//insert node at last of linke list
public void insert(int data)
{
//Create a node
Node node = new Node(data);
if (this.head == null)
{
//When linked list empty add first node
this.head = node;
this.tail = node;
}
else
{
//Add new node at end of linked list
this.tail.next = node;
this.tail = node;
}
}
//Display linked list element
public void display()
{
if (this.head == null)
{
Console.Write("\nEmpty linked list\n");
return;
}
Node temp = this.head;
Console.Write("\n Linked List : ");
//iterating linked list elements
while (temp != null)
{
if (temp != this.head)
{
Console.Write(" →");
}
Console.Write(" " + temp.data);
//visit to next node
temp = temp.next;
}
Console.Write(" → NULL");
}
//Check that left side smaller element exist or not
public Boolean is_left_side_smaller(Node start, Node last)
{
while (start != null && start != last)
{
if (start.data < last.data)
{
return true;
}
start = start.next;
}
return false;
}
//Check that right side smaller element exist or not
public Boolean is_right_side_smaller(Node start)
{
Node temp = start.next;
while (temp != null)
{
if (temp.data < start.data)
{
return true;
}
temp = temp.next;
}
return false;
}
//Find first peak node in given linked list
public void peak_node()
{
//Display linked list elements
this.display();
Node result = null;
if (this.head != null && this.head.next != null)
{
//Define some auxiliary variable
Node current = this.head.next;
//iterating linked list elements
while (current != null && result == null && current.next != null)
{
if (is_left_side_smaller(this.head, current) && is_right_side_smaller(current))
{
result = current;
}
//visit to next node
current = current.next;
}
}
if (result == null)
{
Console.Write("\n Peak node : None\n");
}
else
{
Console.Write("\n Peak node : " + result.data + "\n");
}
}
public static void Main(String[] args)
{
MyLinkedList list1 = new MyLinkedList();
MyLinkedList list2 = new MyLinkedList();
MyLinkedList list3 = new MyLinkedList();
//Add node in first linked list
// 1 → 5 → 6 → 2 → NULL
list1.insert(1);
list1.insert(5);
list1.insert(6);
list1.insert(2);
list1.peak_node();
//Add node in second linked list
// 4 → 6 → 5 → 10 → 3 → NULL
list2.insert(4);
list2.insert(6);
list2.insert(5);
list2.insert(10);
list2.insert(3);
list2.peak_node();
//Add node in third linked list
// 1 → 2 → 4 → NULL
list3.insert(1);
list3.insert(2);
list3.insert(4);
list3.peak_node();
}
}
Output
Linked List : 1 → 5 → 6 → 2 → NULL
Peak node : 5
Linked List : 4 → 6 → 5 → 10 → 3 → NULL
Peak node : 6
Linked List : 1 → 2 → 4 → NULL
Peak node : None
<?php
// Php Program
// Find a peak element in linked list
//Node of LinkedList
class Node
{
public $data;
public $next;
function __construct($data)
{
//Set node value
$this->data = $data;
$this->next = null;
}
}
class MyLinkedList
{
public $head;
public $tail;
//Class constructor
function __construct()
{
$this->head = null;
$this->tail = null;
}
//insert node at last of linke list
public function insert($data)
{
//Create a node
$node = new Node($data);
if ($this->head == null)
{
//When linked list empty add first node
$this->head = $node;
$this->tail = $node;
}
else
{
//Add new node at end of linked list
$this->tail->next = $node;
$this->tail = $node;
}
}
//Display linked list element
public function display()
{
if ($this->head == null)
{
echo "\nEmpty linked list\n";
return;
}
$temp = $this->head;
echo "\n Linked List : ";
//iterating linked list elements
while ($temp != null)
{
if ($temp != $this->head)
{
echo " →";
}
echo " ". $temp->data;
//visit to next node
$temp = $temp->next;
}
echo " → NULL";
}
//Check that left side smaller element exist or not
public function is_left_side_smaller($start, $last)
{
while ($start != null && $start != $last)
{
if ($start->data < $last->data)
{
return true;
}
$start = $start->next;
}
return false;
}
//Check that right side smaller element exist or not
public function is_right_side_smaller($start)
{
$temp = $start->next;
while ($temp != null)
{
if ($temp->data < $start->data)
{
return true;
}
$temp = $temp->next;
}
return false;
}
//Find first peak node in given linked list
public function peak_node()
{
//Display linked list elements
$this->display();
$result = null;
if ($this->head != null && $this->head->next != null)
{
//Define some auxiliary variable
$current = $this->head->next;
//iterating linked list elements
while ($current != null && $result == null && $current->next != null)
{
if ($this->is_left_side_smaller($this->head, $current) && $this->is_right_side_smaller($current))
{
$result = $current;
}
//visit to next node
$current = $current->next;
}
}
if ($result == null)
{
echo "\n Peak node : None\n";
}
else
{
echo "\n Peak node : ". $result->data ."\n";
}
}
}
function main()
{
$list1 = new MyLinkedList();
$list2 = new MyLinkedList();
$list3 = new MyLinkedList();
//Add node in first linked list
// 1 → 5 → 6 → 2 → NULL
$list1->insert(1);
$list1->insert(5);
$list1->insert(6);
$list1->insert(2);
$list1->peak_node();
//Add node in second linked list
// 4 → 6 → 5 → 10 → 3 → NULL
$list2->insert(4);
$list2->insert(6);
$list2->insert(5);
$list2->insert(10);
$list2->insert(3);
$list2->peak_node();
//Add node in third linked list
// 1 → 2 → 4 → NULL
$list3->insert(1);
$list3->insert(2);
$list3->insert(4);
$list3->peak_node();
}
main();
Output
Linked List : 1 → 5 → 6 → 2 → NULL
Peak node : 5
Linked List : 4 → 6 → 5 → 10 → 3 → NULL
Peak node : 6
Linked List : 1 → 2 → 4 → NULL
Peak node : None
// Node Js Program
// Find a peak element in linked list
//Node of LinkedList
class Node
{
constructor(data)
{
//Set node value
this.data = data;
this.next = null;
}
}
class MyLinkedList
{
//Class constructor
constructor()
{
this.head = null;
this.tail = null;
}
//insert node at last of linke list
insert(data)
{
//Create a node
var node = new Node(data);
if (this.head == null)
{
//When linked list empty add first node
this.head = node;
this.tail = node;
}
else
{
//Add new node at end of linked list
this.tail.next = node;
this.tail = node;
}
}
//Display linked list element
display()
{
if (this.head == null)
{
process.stdout.write("\nEmpty linked list\n");
return;
}
var temp = this.head;
process.stdout.write("\n Linked List : ");
//iterating linked list elements
while (temp != null)
{
if (temp != this.head)
{
process.stdout.write(" →");
}
process.stdout.write(" " + temp.data);
//visit to next node
temp = temp.next;
}
process.stdout.write(" → NULL");
}
//Check that left side smaller element exist or not
is_left_side_smaller(start, last)
{
while (start != null && start != last)
{
if (start.data < last.data)
{
return true;
}
start = start.next;
}
return false;
}
//Check that right side smaller element exist or not
is_right_side_smaller(start)
{
var temp = start.next;
while (temp != null)
{
if (temp.data < start.data)
{
return true;
}
temp = temp.next;
}
return false;
}
//Find first peak node in given linked list
peak_node()
{
//Display linked list elements
this.display();
var result = null;
if (this.head != null && this.head.next != null)
{
//Define some auxiliary variable
var current = this.head.next;
//iterating linked list elements
while (current != null && result == null && current.next != null)
{
if (this.is_left_side_smaller(this.head, current) && this.is_right_side_smaller(current))
{
result = current;
}
//visit to next node
current = current.next;
}
}
if (result == null)
{
process.stdout.write("\n Peak node : None\n");
}
else
{
process.stdout.write("\n Peak node : " + result.data + "\n");
}
}
}
function main()
{
var list1 = new MyLinkedList();
var list2 = new MyLinkedList();
var list3 = new MyLinkedList();
//Add node in first linked list
// 1 → 5 → 6 → 2 → NULL
list1.insert(1);
list1.insert(5);
list1.insert(6);
list1.insert(2);
list1.peak_node();
//Add node in second linked list
// 4 → 6 → 5 → 10 → 3 → NULL
list2.insert(4);
list2.insert(6);
list2.insert(5);
list2.insert(10);
list2.insert(3);
list2.peak_node();
//Add node in third linked list
// 1 → 2 → 4 → NULL
list3.insert(1);
list3.insert(2);
list3.insert(4);
list3.peak_node();
}
main();
Output
Linked List : 1 → 5 → 6 → 2 → NULL
Peak node : 5
Linked List : 4 → 6 → 5 → 10 → 3 → NULL
Peak node : 6
Linked List : 1 → 2 → 4 → NULL
Peak node : None
# Python 3 Program
# Find a peak element in linked list
# Node of LinkedList
class Node :
def __init__(self, data) :
# Set node value
self.data = data
self.next = None
class MyLinkedList :
# Class constructor
def __init__(self) :
self.head = None
self.tail = None
# insert node at last of linke list
def insert(self, data) :
# Create a node
node = Node(data)
if (self.head == None) :
# When linked list empty add first node
self.head = node
self.tail = node
else :
# Add new node at end of linked list
self.tail.next = node
self.tail = node
# Display linked list element
def display(self) :
if (self.head == None) :
print("\nEmpty linked list\n", end = "")
return
temp = self.head
print("\n Linked List : ", end = "")
# iterating linked list elements
while (temp != None) :
if (temp != self.head) :
print(" →", end = "")
print(" ", temp.data, end = "")
# visit to next node
temp = temp.next
print(" → NULL", end = "")
# Check that left side smaller element exist or not
def is_left_side_smaller(self, start, last) :
while (start != None and start != last) :
if (start.data < last.data) :
return True
start = start.next
return False
# Check that right side smaller element exist or not
def is_right_side_smaller(self, start) :
temp = start.next
while (temp != None) :
if (temp.data < start.data) :
return True
temp = temp.next
return False
# Find first peak node in given linked list
def peak_node(self) :
# Display linked list elements
self.display()
result = None
if (self.head != None and self.head.next != None) :
# Define some auxiliary variable
current = self.head.next
# iterating linked list elements
while (current != None and result == None and current.next != None) :
if (self.is_left_side_smaller(self.head, current) and self.is_right_side_smaller(current)) :
result = current
# visit to next node
current = current.next
if (result == None) :
print("\n Peak node : None\n", end = "")
else :
print("\n Peak node : ", result.data ,"\n", end = "")
def main() :
list1 = MyLinkedList()
list2 = MyLinkedList()
list3 = MyLinkedList()
# Add node in first linked list
# 1 → 5 → 6 → 2 → NULL
list1.insert(1)
list1.insert(5)
list1.insert(6)
list1.insert(2)
list1.peak_node()
# Add node in second linked list
# 4 → 6 → 5 → 10 → 3 → NULL
list2.insert(4)
list2.insert(6)
list2.insert(5)
list2.insert(10)
list2.insert(3)
list2.peak_node()
# Add node in third linked list
# 1 → 2 → 4 → NULL
list3.insert(1)
list3.insert(2)
list3.insert(4)
list3.peak_node()
if __name__ == "__main__": main()
Output
Linked List : 1 → 5 → 6 → 2 → NULL
Peak node : 5
Linked List : 4 → 6 → 5 → 10 → 3 → NULL
Peak node : 6
Linked List : 1 → 2 → 4 → NULL
Peak node : None
# Ruby Program
# Find a peak element in linked list
# Node of LinkedList
class Node
# Define the accessor and reader of class Node
attr_reader :data, :next
attr_accessor :data, :next
def initialize(data)
# Set node value
self.data = data
self.next = nil
end
end
class MyLinkedList
# Define the accessor and reader of class MyLinkedList
attr_reader :head, :tail
attr_accessor :head, :tail
# Class constructor
def initialize()
self.head = nil
self.tail = nil
end
# insert node at last of linke list
def insert(data)
# Create a node
node = Node.new(data)
if (self.head == nil)
# When linked list empty add first node
self.head = node
self.tail = node
else
# Add new node at end of linked list
self.tail.next = node
self.tail = node
end
end
# Display linked list element
def display()
if (self.head == nil)
print("\nEmpty linked list\n")
return
end
temp = self.head
print("\n Linked List : ")
# iterating linked list elements
while (temp != nil)
if (temp != self.head)
print(" →")
end
print(" ", temp.data)
# visit to next node
temp = temp.next
end
print(" → NULL")
end
# Check that left side smaller element exist or not
def is_left_side_smaller(start, last)
while (start != nil && start != last)
if (start.data < last.data)
return true
end
start = start.next
end
return false
end
# Check that right side smaller element exist or not
def is_right_side_smaller(start)
temp = start.next
while (temp != nil)
if (temp.data < start.data)
return true
end
temp = temp.next
end
return false
end
# Find first peak node in given linked list
def peak_node()
# Display linked list elements
self.display()
result = nil
if (self.head != nil && self.head.next != nil)
# Define some auxiliary variable
current = self.head.next
# iterating linked list elements
while (current != nil && result == nil && current.next != nil)
if (self.is_left_side_smaller(self.head, current) && self.is_right_side_smaller(current))
result = current
end
# visit to next node
current = current.next
end
end
if (result == nil)
print("\n Peak node : None\n")
else
print("\n Peak node : ", result.data ,"\n")
end
end
end
def main()
list1 = MyLinkedList.new()
list2 = MyLinkedList.new()
list3 = MyLinkedList.new()
# Add node in first linked list
# 1 → 5 → 6 → 2 → NULL
list1.insert(1)
list1.insert(5)
list1.insert(6)
list1.insert(2)
list1.peak_node()
# Add node in second linked list
# 4 → 6 → 5 → 10 → 3 → NULL
list2.insert(4)
list2.insert(6)
list2.insert(5)
list2.insert(10)
list2.insert(3)
list2.peak_node()
# Add node in third linked list
# 1 → 2 → 4 → NULL
list3.insert(1)
list3.insert(2)
list3.insert(4)
list3.peak_node()
end
main()
Output
Linked List : 1 → 5 → 6 → 2 → NULL
Peak node : 5
Linked List : 4 → 6 → 5 → 10 → 3 → NULL
Peak node : 6
Linked List : 1 → 2 → 4 → NULL
Peak node : None
// Scala Program
// Find a peak element in linked list
//Node of LinkedList
class Node(var data: Int,
var next: Node)
{
def this(data: Int)
{
this(data, null);
}
}
class MyLinkedList(var head: Node,
var tail: Node)
{
//Class constructor
def this()
{
this(null, null);
}
//insert node at last of linke list
def insert(data: Int): Unit = {
//Create a node
var node: Node = new Node(data);
if (this.head == null)
{
//When linked list empty add first node
this.head = node;
this.tail = node;
}
else
{
//Add new node at end of linked list
this.tail.next = node;
this.tail = node;
}
}
//Display linked list element
def display(): Unit = {
if (this.head == null)
{
print("\nEmpty linked list\n");
return;
}
var temp: Node = this.head;
print("\n Linked List : ");
//iterating linked list elements
while (temp != null)
{
if (temp != this.head)
{
print(" →");
}
print(" " + temp.data);
//visit to next node
temp = temp.next;
}
print(" → NULL");
}
//Check that left side smaller element exist or not
def is_left_side_smaller(start: Node, last: Node): Boolean = {
var temp: Node = start.next;
while (temp != null && start != last)
{
if (temp.data < last.data)
{
return true;
}
temp = temp.next;
}
return false;
}
//Check that right side smaller element exist or not
def is_right_side_smaller(start: Node): Boolean = {
var temp: Node = start.next;
while (temp != null)
{
if (temp.data < start.data)
{
return true;
}
temp = temp.next;
}
return false;
}
//Find first peak node in given linked list
def peak_node(): Unit = {
//Display linked list elements
this.display();
var result: Node = null;
if (this.head != null && this.head.next != null)
{
//Define some auxiliary variable
var current: Node = this.head.next;
//iterating linked list elements
while (current != null && result == null && current.next != null)
{
if (is_left_side_smaller(this.head, current) && is_right_side_smaller(current))
{
result = current;
}
//visit to next node
current = current.next;
}
}
if (result == null)
{
print("\n Peak node : None\n");
}
else
{
print("\n Peak node : " + result.data + "\n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var list1: MyLinkedList = new MyLinkedList();
var list2: MyLinkedList = new MyLinkedList();
var list3: MyLinkedList = new MyLinkedList();
//Add node in first linked list
// 1 → 5 → 6 → 2 → NULL
list1.insert(1);
list1.insert(5);
list1.insert(6);
list1.insert(2);
list1.peak_node();
//Add node in second linked list
// 4 → 6 → 5 → 10 → 3 → NULL
list2.insert(4);
list2.insert(6);
list2.insert(5);
list2.insert(10);
list2.insert(3);
list2.peak_node();
//Add node in third linked list
// 1 → 2 → 4 → NULL
list3.insert(1);
list3.insert(2);
list3.insert(4);
list3.peak_node();
}
}
Output
Linked List : 1 → 5 → 6 → 2 → NULL
Peak node : 5
Linked List : 4 → 6 → 5 → 10 → 3 → NULL
Peak node : 6
Linked List : 1 → 2 → 4 → NULL
Peak node : None
// Swift Program
// Find a peak element in linked list
//Node of LinkedList
class Node
{
var data: Int;
var next: Node? ;
init(_ data: Int)
{
//Set node value
self.data = data;
self.next = nil;
}
}
class MyLinkedList
{
var head: Node? ;
var tail: Node? ;
//Class constructor
init()
{
self.head = nil;
self.tail = nil;
}
//insert node at last of linke list
func insert(_ data: Int)
{
//Create a node
let node: Node? = Node(data);
if (self.head == nil)
{
//When linked list empty add first node
self.head = node;
self.tail = node;
}
else
{
//Add new node at end of linked list
self.tail!.next = node;
self.tail = node;
}
}
//Display linked list element
func display()
{
if (self.head == nil)
{
print("\nEmpty linked list\n", terminator: "");
return;
}
var temp: Node? = self.head;
print("\n Linked List : ", terminator: "");
//iterating linked list elements
while (temp != nil)
{
if (!(temp === self.head))
{
print(" →", terminator: "");
}
print(" ", temp!.data, terminator: "");
//visit to next node
temp = temp!.next;
}
print(" → NULL", terminator: "");
}
//Check that left side smaller element exist or not
func is_left_side_smaller(_ start: Node? , _ last : Node? ) -> Bool
{
var temp: Node? = start!.next;
while (temp != nil && !(start === last))
{
if (temp!.data < last!.data)
{
return true;
}
temp = temp!.next;
}
return false;
}
//Check that right side smaller element exist or not
func is_right_side_smaller(_ start: Node? ) -> Bool
{
var temp: Node? = start!.next;
while (temp != nil)
{
if (temp!.data < start!.data)
{
return true;
}
temp = temp!.next;
}
return false;
}
//Find first peak node in given linked list
func peak_node()
{
//Display linked list elements
self.display();
var result: Node? = nil;
if (self.head != nil && self.head!.next != nil)
{
//Define some auxiliary variable
var current: Node? = self.head!.next;
//iterating linked list elements
while (current != nil && result == nil && current!.next != nil)
{
if (self.is_left_side_smaller(self.head, current) && self.is_right_side_smaller(current))
{
result = current;
}
//visit to next node
current = current!.next;
}
}
if (result == nil)
{
print("\n Peak node : None\n", terminator: "");
}
else
{
print("\n Peak node : ", result!.data ,"\n", terminator: "");
}
}
}
func main()
{
let list1: MyLinkedList = MyLinkedList();
let list2: MyLinkedList = MyLinkedList();
let list3: MyLinkedList = MyLinkedList();
//Add node in first linked list
// 1 → 5 → 6 → 2 → NULL
list1.insert(1);
list1.insert(5);
list1.insert(6);
list1.insert(2);
list1.peak_node();
//Add node in second linked list
// 4 → 6 → 5 → 10 → 3 → NULL
list2.insert(4);
list2.insert(6);
list2.insert(5);
list2.insert(10);
list2.insert(3);
list2.peak_node();
//Add node in third linked list
// 1 → 2 → 4 → NULL
list3.insert(1);
list3.insert(2);
list3.insert(4);
list3.peak_node();
}
main();
Output
Linked List : 1 → 5 → 6 → 2 → NULL
Peak node : 5
Linked List : 4 → 6 → 5 → 10 → 3 → NULL
Peak node : 6
Linked List : 1 → 2 → 4 → NULL
Peak node : None
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