Skip to main content

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




Comment

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

New Comment