Encuentre el valor más grande y el segundo más grande en una Lista Vinculada

Dada una Lista Vinculada , la tarea es encontrar el valor más grande y el segundo más grande en una Lista Vinculada.
Ejemplo: 
 

Entrada: LL = 10 -> 15 -> 5 -> 20 -> 7 -> 9 
Salida: 
Mayor = 20 
Segundo mayor = 15
Entrada: LL = 0 -> 5 -> 52 -> 21 
Salida: 
Mayor = 52 
Segundo mayor = 21 
 

Acercarse: 
 

1. Almacene el máximo de los dos primeros Nodes en una variable max .
2. Almacene el mínimo de los primeros dos Nodes en una variable second_max .
3. Iterar sobre la lista enlazada restante. Para cada Node: 
   • Si el valor del Node actual es mayor que el máximo, establezca second_max como máximo y máximo como el valor del Node actual.
   • De lo contrario, si el valor del Node actual es mayor que second_max, establezca second_max como el valor del Node actual.

A continuación se muestra la implementación del enfoque anterior: 
 

// C++ program to find the largest and
// second largest element in a Linked List
 
#include <bits/stdc++.h>
using namespace std;
 
// Link list node
struct Node {
    int data;
    struct Node* next;
};
 
// Function to push the node at the
// beginning of the linked list
void push(struct Node** head_ref,
          int new_data)
{
    struct Node* new_node
        = (struct Node*)malloc(
            sizeof(struct Node));
 
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}
 
// Function to print the largest
// and second largest element
void findLargestAndSecondLargest(struct Node* head)
{
    // initialise max and second max using
    // first two nodes of linked list
    int val1 = head->data,
        val2 = head->next->data,
        max = std::max(val1, val2),
        second_max = std::min(val1, val2);
 
    // move the head pointer to 3rd node
    head = head->next->next;
 
    // iterate over rest of linked list
    while (head != NULL) {
 
        if (head->data > max) {
 
            // If current node value is greater
            // than max, then set second_max as
            // current max value and max as
            // current node value
            second_max = max;
            max = head->data;
        }
        else if (head->data > second_max) {
 
            // else if current node value is
            // greater than second_max, set
            // second_max as node value
            second_max = head->data;
        }
 
        // move the head pointer to next node
        head = head->next;
    }
 
    // Print the largest
    // and second largest value
    cout << "Largest = "
         << max << endl;
    cout << "Second Largest = "
         << second_max << endl;
}
 
// Driver code
int main()
{
    struct Node* head = NULL;
 
    push(&head, 20);
    push(&head, 5);
    push(&head, 15);
    push(&head, 10);
    push(&head, 7);
    push(&head, 6);
    push(&head, 11);
    push(&head, 9);
 
    findLargestAndSecondLargest(head);
 
    return 0;
}

// Java program to find the largest and
// second largest element in a Linked List
class GFG{
  
// Link list node
static class Node {
    int data;
    Node next;
 
};
  
// Function to push the 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 print the largest
// and second largest element
static void findLargestAndSecondLargest(Node head)
{
    // initialise max and second max using
    // first two nodes of linked list
    int val1 = head.data,
        val2 = head.next.data,
        max = Math.max(val1, val2),
        second_max = Math.min(val1, val2);
  
    // move the head pointer to 3rd node
    head = head.next.next;
  
    // iterate over rest of linked list
    while (head != null) {
  
        if (head.data > max) {
  
            // If current node value is greater
            // than max, then set second_max as
            // current max value and max as
            // current node value
            second_max = max;
            max = head.data;
        }
        else if (head.data > second_max) {
  
            // else if current node value is
            // greater than second_max, set
            // second_max as node value
            second_max = head.data;
        }
  
        // move the head pointer to next node
        head = head.next;
    }
  
    // Print the largest
    // and second largest value
    System.out.print("Largest = "
         + max +"\n");
    System.out.print("Second Largest = "
         + second_max +"\n");
}
  
// Driver code
public static void main(String[] args)
{
    Node head = null;
  
    head = push(head, 20);
    head = push(head, 5);
    head = push(head, 15);
    head = push(head, 10);
    head = push(head, 7);
    head = push(head, 6);
    head = push(head, 11);
    head = push(head, 9);
  
    findLargestAndSecondLargest(head);
}
}
 
// This code is contributed by Rajput-Ji

# Python3 program to find the largest and
# second largest element in a Linked List
# Node class
class Node:
     
    # Function to initialize the node object
    def __init__(self, data):
         
        # Assign data
        self.data = data
         
        # Initialize
        # next as null
        self.next = None
     
# Linked List Class
class LinkedList:
 
    # Function to initialize the
    # LinkedList class.
    def __init__(self):
         
        # Initialize head as None
        self.head = None
 
    # This function insert a new node at the
    # beginning of the linked list
    def push(self, new_data):
     
        # Create a new Node
        new_node = Node(new_data)
 
        # Make next of new Node as head
        new_node.next = self.head
 
        # Move the head to point to new Node
        self.head = new_node
 
    # Function to find the max and
    # second largest value from the list
    def findLargestAndSecondLargest(self):
 
        # Take a Head to iterate list
        Head = self.head
 
        # Initialize max and second_max
        # using first two nodes of the list
        val1 = Head.data
        val2 = Head.next.data
        Max = max(val1, val2)
        second_max = min(val1, val2)
 
        # Move the Head to third node
        Head = Head.next.next
 
        # Iterate over rest of linked list
        while(Head != None):
 
            # If current node value is
            # greater then Max then
            if(Head.data > Max):
 
                # Set the current max to second_max
                # and current node value to max
                second_max = Max
                Max = Head.data
 
            # Else if current node value is
            # greater then second_max value
            elif(Head.data > second_max):
 
                # Then current node value
                # to second_max
                second_max = Head.data
 
            # Move the head to next node
            Head = Head.next
 
        # Print the largest and second largest values
        print("Largest = ", Max)
        print("Second Largest = ", second_max)
 
# Driver code
if __name__ == '__main__':
 
    # Initialising the linked list
    head = LinkedList()
 
    # Pushing the values in list
    head.push(20)
    head.push(5)
    head.push(15)
    head.push(10)
    head.push(7)
    head.push(6)
    head.push(11)
    head.push(9)
     
    # Calling the function to print
    # largest and second largest values.
    head.findLargestAndSecondLargest()
             
# This code is contributed by Amit Mangal.

// C# program to find the largest and
// second largest element in a Linked List
using System;
 
class GFG{
   
// Link list node
class Node {
    public int data;
    public Node next;
  
};
   
// Function to push the 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 print the largest
// and second largest element
static void findLargestAndSecondLargest(Node head)
{
    // initialise max and second max using
    // first two nodes of linked list
    int val1 = head.data,
        val2 = head.next.data,
        max = Math.Max(val1, val2),
        second_max = Math.Min(val1, val2);
   
    // move the head pointer to 3rd node
    head = head.next.next;
   
    // iterate over rest of linked list
    while (head != null) {
   
        if (head.data > max) {
   
            // If current node value is greater
            // than max, then set second_max as
            // current max value and max as
            // current node value
            second_max = max;
            max = head.data;
        }
        else if (head.data > second_max) {
   
            // else if current node value is
            // greater than second_max, set
            // second_max as node value
            second_max = head.data;
        }
   
        // move the head pointer to next node
        head = head.next;
    }
   
    // Print the largest
    // and second largest value
    Console.Write("Largest = "
         + max +"\n");
    Console.Write("Second Largest = "
         + second_max +"\n");
}
   
// Driver code
public static void Main(String[] args)
{
    Node head = null;
   
    head = push(head, 20);
    head = push(head, 5);
    head = push(head, 15);
    head = push(head, 10);
    head = push(head, 7);
    head = push(head, 6);
    head = push(head, 11);
    head = push(head, 9);
   
    findLargestAndSecondLargest(head);
}
}
 
// This code is contributed by Princi Singh

<script>
 
// Javascript program to find the largest and
// second largest element in a Linked List
 
// Link list node
class Node {
 
    constructor()
    {
        this.data = 0;
        this.next = null;
    }
};
 
// Function to push the 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 print the largest
// and second largest element
function findLargestAndSecondLargest(head)
{
    // initialise max and second max using
    // first two nodes of linked list
    var val1 = head.data,
        val2 = head.next.data,
        max = Math.max(val1, val2),
        second_max = Math.min(val1, val2);
 
    // move the head pointer to 3rd node
    head = head.next.next;
 
    // iterate over rest of linked list
    while (head != null) {
 
        if (head.data > max) {
 
            // If current node value is greater
            // than max, then set second_max as
            // current max value and max as
            // current node value
            second_max = max;
            max = head.data;
        }
        else if (head.data > second_max) {
 
            // else if current node value is
            // greater than second_max, set
            // second_max as node value
            second_max = head.data;
        }
 
        // move the head pointer to next node
        head = head.next;
    }
 
    // Print the largest
    // and second largest value
    document.write( "Largest = "
         + max + "<br>");
    document.write( "Second Largest = "
         + second_max + "<br>");
}
 
// Driver code
var head = null;
head = push(head, 20);
head = push(head, 5);
head = push(head, 15);
head = push(head, 10);
head = push(head, 7);
head = push(head, 6);
head = push(head, 11);
head = push(head, 9);
findLargestAndSecondLargest(head);
 
// This code is contributed by noob2000.
</script>

Largest = 20
Second Largest = 15

Análisis de rendimiento : 
 

• Complejidad de tiempo : en el enfoque anterior, como estamos iterando sobre la lista enlazada solo una vez, la complejidad de tiempo es O(N) .
• Complejidad del espacio auxiliar : en el enfoque anterior, no estamos utilizando ningún espacio adicional aparte de algunas variables de tamaño constante, por lo que la complejidad del espacio auxiliar es O(1) .