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

Your email address will not be published.