C++ program to find the second largest element in a Linked list
In 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