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

2021年5月16日17:10:45 发表评论 958 次浏览

## 本文概述

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;

struct Node {
int data;
struct Node* next;
};

//Function to push the node at the
void push( struct Node** head_ref, int new_data)
{
struct Node* new_node
= ( struct Node*) malloc (
sizeof ( struct Node));

new_node->data = new_data;
}

//Function to print the largest
//and second largest element
{
//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

//iterate over rest of linked list

//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;
}

//else if current node value is
//greater than second_max, set
//second_max as node value
}

//move the head pointer to next node
}

//Print the largest
//and second largest value
cout <<"Largest = "
<<max <<endl;
cout <<"Second Largest = "
<<second_max <<endl;
}

//Driver code
int main()
{

return 0;
}``````

## Java

``````//Java program to find the largest and
//second largest element in a Linked List
class GFG{

static class Node {
int data;
Node next;

};

//Function to push the node at the
static Node push(Node head_ref, int new_data)
{
Node new_node
= new Node();

new_node.data = new_data;
}

//Function to print the largest
//and second largest element
{
//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

//iterate over rest of linked list
while (head != null ) {

//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;
}

//else if current node value is
//greater than second_max, set
//second_max as node value
}

//move the head pointer to next node
}

//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)
{

}
}

//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 = data

# Initialize
# next as null
self . next = None

# Function to initialize the
def __init__( self ):

# 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

# Move the head to point to new Node

# Function to find the max and
# second largest value from the list
def findLargestAndSecondLargest( self ):

# Take a Head to iterate list

# Initialize max and second_max
# using first two nodes of the list
Max = max (val1, val2)
second_max = min (val1, val2)

# Move the Head to third node

# Iterate over rest of linked list
while (Head ! = None ):

# If current node value is
# greater then Max then

# Set the current max to second_max
# and current node value to max
second_max = Max

# Else if current node value is
# greater then second_max value

# Then current node value
# to second_max

# Move the head to next node

# Print the largest and second largest values
print ( "Largest = " , Max )
print ( "Second Largest = " , second_max)

# Driver code
if __name__ = = '__main__' :

# Pushing the values in list

# Calling the function to print
# largest and second largest values.

# 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{

class Node {
public int data;
public Node next;

};

//Function to push the node at the
static Node push(Node head_ref, int new_data)
{
Node new_node
= new Node();

new_node.data = new_data;
}

//Function to print the largest
//and second largest element
{
//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

//iterate over rest of linked list
while (head != null ) {

//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;
}

//else if current node value is
//greater than second_max, set
//second_max as node value
}

//move the head pointer to next node
}

//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)
{

}
}

//This code is contributed by Princi Singh``````

``````Largest = 20
Second Largest = 15``````

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