C++-Programm: Finden Sie das zweitkleinste Element in einer verknüpften Liste

Eine geordnete Sammlung von Datenelementen. Jedes Datenelement hat einen Link zu seinem nächsten Element (manchmal zu seinem vorherigen Element). Vorausgesetzt, es gibt eine verknüpfte Liste, müssen wir das zweitkleinste Element finden. Unten ist das folgende Szenario.

Nehmen wir einige einfache Eingabe- und Ausgabeszenarien an

Nehmen Sie dieses Szenario an, wir haben eine verknüpfte Liste, die darin enthaltenen Elemente sind "8->4->6->2->9,". Nachdem die gesamte verknüpfte Liste iteriert wurde, ist das zweitkleinste Element 8.

Input = 8->4->6->2->9
Output = 8

Programmierimplementierung der verknüpften Liste

Node* head = new Node(8);
head->next = new Node(4);
head->next->next = new Node(6);
head->next->next->next = new Node(2);
head->next->next->next->next = new Node(9);
result = solve(head);

Betrachten Sie einen anderen Fall, in dem jedes Element in der verknüpften Liste denselben Wert hat. Nach dem Durchlaufen aller Elemente wird das zweitkleinste Element nicht in der verknüpften Liste gefunden. Da jedes Element in der verknüpften Liste denselben Wert enthält.

Input = 1->1->1->1->1->1
Output = There is no second smallest element in Linked list

Algorithmus

Hier sind die Schritte, die Sie bei der Ausführung der Aufgabe befolgen müssen

• Weisen Sie zwei Variablen zu (S1, S2)

• S1 speichert das kleinste Element in der verknüpften Liste

• S2 enthält das zweitkleinste Element in der verknüpften Liste.

• Bei jeder Iteration wird das kleinste Element nach S1 verschoben, und wenn es angetroffen wird, wird es nach S2 verschoben

• Wenn das Minimum (S1) kleiner als der neue kleinere Wert ist, wird der neue kleinere zum Minimum (S1).

• Der neue kleinere wird kleiner (S1) und der kleinere (S1) wandert zum zweiten kleineren (S2).

• Nach jedem möglichen Durchlauf ist das zweitkleinste Element in der endgültigen Ausgabe die Ausgabe.

Beispiel

In der C++-Implementierung können wir zwei Variablen beibehalten. 1 ist das kleinste, andere ist das zweitkleinste, und dann wird die verknüpfte Liste jedes Mal durchlaufen, wenn ein kleineres Element angetroffen wird, die kleinste Variable wird auf die nächstkleinere aktualisiert und die neue kleinere wird zur kleinsten. Wenn also ein Element kleiner als das kleinste Element ist, wird das zweitkleinste Element zum kleinsten und das kleinste Element zum neuen Element. Wenn nicht, vergleichen wir das zweitkleinste Element und stellen fest, ob das aktuelle Element kleiner als das zweitkleinste Element ist, und aktualisieren es entsprechend.

#include <iostream>
using namespace std;
class Node {
   public:
   int val;
   Node *next;
   Node(int val) {
      this->val = val;
      next = NULL;
   }
};
int solve(Node* root) {
   int s1=root->val, s2=root->val;
   while(root) {
      if(root->val <= s1) {
         s2 = s1;
         s1 = root->val;
      } else if(root->val < s2) {
         s2 = root->val;
      }
      root = root->next;
   }
   return s2;
}
int main() {
   Node* head = new Node(5);
   head->next = new Node(8);
   head->next->next = new Node(9);
   head->next->next->next = new Node(2);
   head->next->next->next->next = new Node(4);
   cout << "Second smallest element in the linked list is : " << solve(head);
   return 0;
}

Ausgabe

Second smallest element in the linked list is: 4

Fazit

Durchlaufen Sie die verknüpfte Liste einmal, die zeitliche Komplexität beträgt O(n). Wenn Sie die oben genannten Informationen nützlich fanden, besuchen Sie unsere offizielle Website, um weitere verwandte Themen zum Thema Programmierung zu erfahren.

Das obige ist der detaillierte Inhalt vonC++-Programm: Finden Sie das zweitkleinste Element in einer verknüpften Liste. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!