C++ program to find the second largest element in a Linked list
By Abinash ReddyIn this article, we will learn to find the second largest element in a Linked list in C++. A linked list is a linear collection of data(nodes) that are stored randomly in the memory. In liked list, each node has two components one is data and the other is a link to the next node.
Examples
Input: 34 -> 2 -> 4 -> 12 -> 67 ->5 Output: 34 Input: 1 -> 2 -> 3 -> 4 Output: 3
Finding the second largest element in a Linked list in C++
1. Declare two variables maxi and sec_max and store the maximum and minimum value between the first two nodes respectively.
2. Traverse the given linked list for each node check
- If the current node data is greater than the maxi then set sec_max as maxi and maxi as current node data.
- If the current node data is greater than the sec_node then set sec_max as current node data.
3. Finally, return the sec_max value.
#include <bits/stdc++.h>
using namespace std;
struct Node{
int data;
struct Node* next;
};
// fucntion to insert new node at the begining of the linked list
void insert(Node** head, int data){
Node* new_node = new Node;
new_node->data = data;
new_node->next = (*head);
(*head) = new_node;
}
// function to print the list
void print_list(Node* head){
while (head != NULL)
{
cout<<head->data<<" ";
head = head->next;
}
}
// function to find the second largest element
int SecondLargest(Node* head){
int v1 = head->data;
int v2 = head->next->data;
int maxi = max(v1, v1);
int sec_max = min(v1, v2);
head = head->next->next;
while (head != NULL){
if (head->data > maxi){
sec_max = maxi;
maxi = head->data;
}
else if(head->data > sec_max){
sec_max = head->data;
}
head = head->next;
}
return sec_max;
}
int main(){
Node* head = NULL;
insert(&head, 3);
insert(&head, 12);
insert(&head, 89);
insert(&head, 42);
insert(&head, 5);
insert(&head, 62);
cout<<"The given linked list is: ";
print_list(head);
cout<<"\n";
cout<<"The second largest element in the list is: "<<SecondLargest(head);
return 0;
}Output
The given linked list is: 62 5 42 89 12 3 The second largest element in the list is: 62
Also, read
Leave a Reply