Programme C++ : Trouver le deuxième plus petit élément dans une liste chaînée

Une collection ordonnée d'éléments de données, chaque élément de données a un lien vers son élément suivant (parfois son élément précédent), en supposant qu'il existe une liste chaînée, alors nous devons trouver le deuxième plus petit élément. Vous trouverez ci-dessous le scénario suivant.

Supposons quelques scénarios d'entrée et de sortie simples

Supposons ce scénario, nous avons une liste chaînée, les éléments qu'elle contient sont "8->4->6->2->9,". Ensuite, après avoir parcouru toute la liste chaînée, le deuxième plus petit élément est 8.

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

Mise en œuvre de la programmation de la liste chaînée

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);

Considérons un autre cas où chaque élément de la liste chaînée a la même valeur. Après avoir parcouru tous les éléments, le deuxième plus petit élément ne sera pas trouvé dans la liste chaînée. Puisque chaque élément de la liste chaînée contient la même valeur.

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

Algorithme

Voici les étapes à suivre lors de l'exécution de la tâche

• Attribuer deux variables (S1, S2)

• S1 enregistrera le plus petit élément de la liste chaînée

• S2 contiendra le deuxième plus petit élément de la liste chaînée.

• À chaque itération, le plus petit élément sera déplacé vers S1, et lorsqu'il sera rencontré, il sera déplacé vers S2

• Lorsque le minimum (S1) est inférieur à la nouvelle valeur plus petite, la nouvelle plus petite deviendra le minimum (S1).

• Le nouveau plus petit deviendra plus petit (S1) et le plus petit (S1) passera au deuxième plus petit (S2).

• Après chaque parcours possible, le deuxième plus petit élément de la sortie finale sera la sortie.

Exemple

Dans l'implémentation C++, nous pouvons conserver 2 variables. 1 est le plus petit, other est le deuxième plus petit, puis la liste chaînée est parcourue chaque fois qu'un élément plus petit est rencontré, la plus petite variable est mise à jour vers la plus petite suivante et la nouvelle plus petite devient la plus petite. Ainsi, chaque fois qu’un élément est plus petit que le plus petit élément, le deuxième plus petit élément devient le plus petit et le plus petit élément devient le nouvel élément. Sinon, nous comparons le deuxième plus petit élément et déterminons si l'élément actuel est plus petit que le deuxième plus petit élément, et mettons à jour en conséquence.

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

Sortie

Second smallest element in the linked list is: 4

Conclusion

Parcourez la liste chaînée une fois, la complexité temporelle est O(n). Si vous avez trouvé les informations ci-dessus utiles, visitez notre site Web officiel pour en savoir plus sur les sujets liés à la programmation.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!