在链表中找到最大和第二大的值

本文概述

  • C ++
  • Java
  • Python3
  • C#
【在链表中找到最大和第二大的值】给定一个链表, 任务是在链表中找到最大和第二大的值。
例子:
输入:LL = 10-> 15-> 5-> 20-> 7-> 9
输出:最大= 20
第二最大= 15
输入:LL = 0-> 5-> 52-> 21
输出:最大= 52
第二最大= 21
方法:
  1. 将前两个节点的最大值存储在变量中最高.
  2. 将前两个节点中的最小值存储在变量中second_max.
  3. 遍历其余的链表。对于每个节点:
    • 如果当前节点的值大于max, 则将second_max设置为max, 将max设置为当前节点的值。
    • 否则, 如果当前节点的值大于second_max, 则将second_max设置为当前节点的值。
下面是上述方法的实现:
C ++
//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 = https://www.lsbin.com/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
//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 = https://www.lsbin.com/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
# 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 = https://www.lsbin.com/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#
//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 = https://www.lsbin.com/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

输出如下:
Largest = 20 Second Largest = 15

绩效分析:
  • 时间复杂度:在上述方法中, 由于我们仅对链表进行迭代一次, 因此时间复杂度为上).
  • 辅助空间复杂度:在上述方法中, 除了几个恒定大小的变量之外, 我们没有使用任何额外的空间, 因此辅助空间的复杂度为O(1).

    推荐阅读