Given a Linked list of integers. The task is to find a peak element in it. An element in the list is said to be peak if it is NOT smaller than its neighbors. For corner elements, we need to consider only one neighbor.
For example:
- If the input list is {5 -> 10 -> 20 -> 15}, 20 is the only peak element.
- For input list {10 -> 20 -> 15 -> 2 -> 23 -> 90 -> 67}, there are two peak elements: 20 and 90. Note that it is needed to return any one peak element.
Following corner cases give a better idea about the problem:
- If the input list is sorted in strictly increasing order, the last element is always a peak element. For example, 50 is peak element in {10 -> 20 -> 30 -> 40 -> 50}.
- If the input list is sorted in strictly decreasing order, the first element is always a peak element. 100 is the peak element in {100 -> 80 -> 60 -> 50 -> 20}.
- If all elements of the input list are same, every element is a peak element.
Examples:
Input : List = {1 -> 6 -> 8 -> 4 -> 12} Output : 8 Input : List = {10 -> 20 -> 15 -> 2 -> 23 -> 90 -> 67} Output : 90
The idea is to traverse the linked list and check if the current element is a peak element or not. If yes then return the current element else move forward in the list.
The current element will be a peak element if it is greater than its previous and next elements.
Below program illustrate the above approach:
C++
// C++ implementation to find the peak // element in the Linked List #include <bits/stdc++.h> using namespace std; /* A Linked list node */ struct Node { int data; struct Node* next; }; // function to insert a node at the // beginning of the linked list void push( struct Node** head_ref, int new_data) { struct Node* new_node = new Node; new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } // Function to find the peak element int findPeak( struct Node* head) { // Return -1 to indicate that // peak does not exist if (head == NULL) return -1; // If there is only one node if (head->next == NULL) return head->data; // Traverse till last node (starting from // second node) int prev = head->data; Node *curr; for (curr = head->next; curr->next != NULL; curr = curr->next) { // check if current node is greater // than both neighbours if (curr->data > curr->next->data && curr->data > prev) return curr->data; prev = curr->data; } // We reach here when curr is last node if (curr->data > prev) return curr->data; // Peak does not exists else return -1; } // Driver program int main() { struct Node* head = NULL; // create linked list 1->6->8->4->12 push(&head, 12); push(&head, 4); push(&head, 8); push(&head, 6); push(&head, 1); cout << "Peak element is: " << findPeak(head); return 0; } |
Java
// Java implementation to find the peak // element in the Linked List class GFG { // A Linked list node / static class Node { int data; Node next; }; // function to insert a node at the // beginning of the linked list static Node push( Node head_ref, int new_data) { Node new_node = new Node(); new_node.data = new_data; new_node.next = (head_ref); (head_ref) = new_node; return head_ref; } // Function to find the peak element static int findPeak( Node head) { // Return -1 to indicate that // peak does not exist if (head == null ) return - 1 ; // If there is only one node if (head.next == null ) return head.data; // Traverse till last node (starting from // second node) int prev = head.data; Node curr; for (curr = head.next; curr.next != null ; curr = curr.next) { // check if current node is greater // than both neighbours if (curr.data > curr.next.data && curr.data > prev) return curr.data; prev = curr.data; } // We reach here when curr is last node if (curr.data > prev) return curr.data; // Peak does not exists else return - 1 ; } // Driver program public static void main(String args[]) { Node head = null ; // create linked list 1.6.8.4.12 head=push(head, 12 ); head=push(head, 4 ); head=push(head, 8 ); head=push(head, 6 ); head=push(head, 1 ); System.out.print( "Peak element is: " + findPeak(head)); } } // This code is contributed by Arnab Kundu |
Python3
# Python3 implementation to find the peak # element in the Linked List # Link list node class Node : def __init__( self ): self .data = 0 self . next = None # function to insert a node at the # beginning of the linked list def push( head_ref, new_data) : new_node = Node() new_node.data = new_data new_node. next = (head_ref) (head_ref) = new_node return head_ref # Function to find the peak element def findPeak( head): # Return -1 to indicate that # peak does not exist if (head = = None ) : return - 1 # If there is only one node if (head. next = = None ) : return head.data # Traverse till last node (starting from # second node) prev = head.data curr = head. next while ( curr. next ! = None ): # check if current node is greater # than both neighbours if (curr.data > curr. next .data and curr.data > prev) : return curr.data prev = curr.data curr = curr. next # We reach here when curr is last node if (curr.data > prev) : return curr.data # Peak does not exists else : return - 1 # Driver program head = None # create linked list 1.6.8.4.12 head = push(head, 12 ) head = push(head, 4 ) head = push(head, 8 ) head = push(head, 6 ) head = push(head, 1 ) print ( "Peak element is: " , findPeak(head)) # This code is contributed by Arnab Kundu |
C#
// C# implementation to find the peak // element in the Linked List using System; class GFG { // A Linked list node / public class Node { public int data; public Node next; }; // function to insert a node at the // beginning of the linked list static Node push(Node head_ref, int new_data) { Node new_node = new Node(); new_node.data = new_data; new_node.next = (head_ref); (head_ref) = new_node; return head_ref; } // Function to find the peak element static int findPeak(Node head) { // Return -1 to indicate that // peak does not exist if (head == null ) return -1; // If there is only one node if (head.next == null ) return head.data; // Traverse till last node // (starting from second node) int prev = head.data; Node curr; for (curr = head.next; curr.next != null ; curr = curr.next) { // check if current node is greater // than both neighbours if (curr.data > curr.next.data && curr.data > prev) return curr.data; prev = curr.data; } // We reach here when curr is last node if (curr.data > prev) return curr.data; // Peak does not exists else return -1; } // Driver Code public static void Main(String[] args) { Node head = null ; // create linked list 1.6.8.4.12 head = push(head, 12); head = push(head, 4); head = push(head, 8); head = push(head, 6); head = push(head, 1); Console.Write( "Peak element is: " + findPeak(head)); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // JavaScript implementation to find the peak // element in the Linked List // A Linked list node / class Node { constructor() { this .data = 0; this .next = null ; } } // function to insert a node at the // beginning of the linked list function push(head_ref, new_data) { var new_node = new Node(); new_node.data = new_data; new_node.next = head_ref; head_ref = new_node; return head_ref; } // Function to find the peak element function findPeak(head) { // Return -1 to indicate that // peak does not exist if (head == null ) return -1; // If there is only one node if (head.next == null ) return head.data; // Traverse till last node // (starting from second node) var prev = head.data; var curr; for (curr = head.next; curr.next != null ; curr = curr.next) { // check if current node is greater // than both neighbours if (curr.data > curr.next.data && curr.data > prev) return curr.data; prev = curr.data; } // We reach here when curr is last node if (curr.data > prev) return curr.data; // Peak does not exists else return -1; } // Driver Code var head = null ; // create linked list 1.6.8.4.12 head = push(head, 12); head = push(head, 4); head = push(head, 8); head = push(head, 6); head = push(head, 1); document.write( "Peak element is: " + findPeak(head)); </script> |
Peak element is: 8
Time Complexity: O(N) where N is the number of elements in the linked list.
Space Complexity: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!