Dada una lista enlazada de datos enteros. La tarea es escribir un programa que encuentre eficientemente el segundo elemento más pequeño presente en la Lista Enlazada.
Ejemplos:
Input : List = 12 -> 35 -> 1 -> 10 -> 34 -> 1 Output : The second smallest element is 10. Input : List = 10 -> 5 -> 10 Output : The second largest element is 10.
Una solución simple será ordenar primero la lista vinculada en orden ascendente y luego imprimir el segundo elemento de la lista vinculada ordenada. La complejidad temporal de esta solución es O(nlogn).
Una solución mejor es recorrer la lista Vinculada dos veces. En el primer recorrido encuentre el elemento mínimo. En el segundo recorrido encuentre el elemento más pequeño mayor que el elemento obtenido en el primer recorrido. La complejidad temporal de esta solución es O(n). Una solución
más eficiente puede ser encontrar el segundo elemento más pequeño en un solo recorrido.
C++
// C++ program to print second smallest
// value in a linked list
#include <climits>
#include <iostream>
using namespace std;
// A linked list node
struct Node {
int data;
struct Node* next;
};
// Function to add a node at the
// beginning of Linked List
void push(struct Node** head_ref, int new_data)
{
struct Node* new_node = new Node;
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
// Function to print the second
// smallest element
void print2smallest(struct Node* head)
{
int first = INT_MAX, second = INT_MAX;
struct Node* temp = head;
while (temp != NULL) {
if (temp->data < first) {
second = first;
first = temp->data;
}
// If current node's data is in between
// first and second then update second
else if (temp->data < second && temp->data != first)
second = temp->data;
temp = temp->next;
}
if (second == INT_MAX)
cout << "There is no second smallest element\n";
else
cout << "The second smallest element is " << second;
}
// Driver program to test above function
int main()
{
struct Node* start = NULL;
/* The constructed linked list is:
12 -> 35 -> 1 -> 10 -> 34 -> 1 */
push(&start, 1);
push(&start, 34);
push(&start, 10);
push(&start, 1);
push(&start, 35);
push(&start, 12);
print2smallest(start);
return 0;
}
Java
// Java program to print second smallest
// value in a linked list
class GFG
{
// A linked list node
static class Node
{
int data;
Node next;
};
// Function to add a node at the
// beginning of 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 new_node;
}
// Function to print the second
// smallest element
static void print2smallest(Node head)
{
int first = Integer.MAX_VALUE,
second = Integer.MAX_VALUE;
Node temp = head;
while (temp != null)
{
if (temp.data < first)
{
second = first;
first = temp.data;
}
// If current node's data is in between
// first and second then update second
else if (temp.data < second && temp.data != first)
second = temp.data;
temp = temp.next;
}
if (second == Integer.MAX_VALUE)
System.out.print("There is no second smallest element\n");
else
System.out.print("The second smallest element is " + second);
}
// Driver code
public static void main(String[] args)
{
Node start = null;
/* The constructed linked list is:
12.35.1.10.34.1 */
start = push(start, 1);
start = push(start, 34);
start = push(start, 10);
start = push(start, 1);
start = push(start, 35);
start = push(start, 12);
print2smallest(start);
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 program to print second smallest
# value in a linked list
# A linked list node
class Node :
def __init__(self):
self.data = 0
self.next = None
# Function to add a node at the
# beginning of Linked List
def push(head_ref, new_data):
new_node = Node()
new_node.data = new_data
new_node.next = head_ref
head_ref = new_node
return new_node
# Function to print the second
# smallest element
def print2smallest(head):
first = 32676
second = 32676
temp = head
while (temp != None):
if (temp.data < first):
second = first
first = temp.data
# If current node's data is in between
# first and second then update second
elif (temp.data < second and temp.data != first):
second = temp.data
temp = temp.next
if (second == 32676):
print("There is no second smallest element")
else:
print("The second smallest element is " , second)
# Driver code
start = None
# The constructed linked list is:
# 12.35.1.10.34.1
start = push(start, 1)
start = push(start, 34)
start = push(start, 10)
start = push(start, 1)
start = push(start, 35)
start = push(start, 12)
print2smallest(start)
# This code is contributed by Arnab Kundu
C#
// C# program to print second smallest
// value in a linked list
using System;
class GFG
{
// A linked list node
class Node
{
public int data;
public Node next;
};
// Function to add a node at the
// beginning of 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 new_node;
}
// Function to print the second
// smallest element
static void print2smallest(Node head)
{
int first = int.MaxValue,
second = int.MaxValue;
Node temp = head;
while (temp != null)
{
if (temp.data < first)
{
second = first;
first = temp.data;
}
// If current node's data is in between
// first and second then update second
else if (temp.data < second &&
temp.data != first)
second = temp.data;
temp = temp.next;
}
if (second == int.MaxValue)
Console.Write("There is no second smallest element\n");
else
Console.Write("The second smallest element is " +
second);
}
// Driver code
public static void Main(String[] args)
{
Node start = null;
/* The constructed linked list is:
12 -> 35 -> 1 -> 10 -> 34 -> 1 */
start = push(start, 1);
start = push(start, 34);
start = push(start, 10);
start = push(start, 1);
start = push(start, 35);
start = push(start, 12);
print2smallest(start);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program to print second smallest
// value in a linked list
// Structure to represent a node of the tree
class Node {
constructor() {
this.data = 0;
this.next = null;
}
}
// Function to add a node at the
// beginning of 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 new_node;
}
// Function to print the second
// smallest element
function print2smallest( head)
{
let first = Number.MAX_VALUE ,
second = Number.MAX_VALUE ;
var temp = head;
while (temp != null)
{
if (temp.data < first)
{
second = first;
first = temp.data;
}
// If current node's data is in between
// first and second then update second
else if (temp.data < second && temp.data != first)
second = temp.data;
temp = temp.next;
}
if (second == Number.MAX_VALUE )
document.write("There is no second smallest element" + "</br>");
else
document.write("The second smallest element is " + second);
}
// Driver Code
var start = null;
/* The constructed linked list is:
12.35.1.10.34.1 */
start = push(start, 1);
start = push(start, 34);
start = push(start, 10);
start = push(start, 1);
start = push(start, 35);
start = push(start, 12);
print2smallest(start);
// This code is contributed by jana_sayantan.
</script>
Producción:
The second smallest element is 10
Complejidad del tiempo : O(n)
Publicación traducida automáticamente
Artículo escrito por gfg_sal_gfg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA