Programme C++ : remplacez les nœuds en double dans la liste chaînée par des copies

Dans cet article, on nous donne une liste chaînée contenant des éléments de 1 à n avec des doublons. Les éléments 1 à n existeront toujours avec des doublons dans [1..n]. Nous devons remplacer chaque élément répété par n+1, n+2, etc.

Prenons un exemple

1 → 2 → 2 → 4 → 5 → 3 → 6 → 6

Suivant n = 42. Ainsi, chaque doublon est remplacé par n+1, n+2, etc. Les 42 suivants sont remplacés par 47, les 46 suivants sont remplacés par 48 et la première instance reste intacte.

Tout d'abord, nous devons construire un arbre binaire dans la méthode principale comme indiqué ci-dessous -

Node* head = new Node(1);
head->next = new Node(2);
head->next->next = new Node(2);
head->next->next->next = new Node(4);
head->next->next->next->next = new Node(5);
head->next->next->next->next->next = new Node(3);
head->next->next->next->next->next->next = new Node(6);
head->next->next->next->next->next->next->next = new Node(6);
solve(head);

Maintenant, les nœuds sont les suivants :

1 → 2 → 7 → 4 → 5 → 3 → 6 → 8

Comme nous l'avons observé, nous devons garder une trace des éléments que nous voyons pour trouver la valeur de départ de n. Nous avons également besoin d'un mécanisme pour déterminer quels éléments sont répétés pour remplacer leurs valeurs.

La structure de données proposée qui vient immédiatement à l'esprit est identifiée. Nous pouvons parcourir la liste chaînée et insérer des éléments dans la collection. Après avoir poussé les éléments de l'ensemble, nous pouvons trouver le dernier élément, qui est le plus grand élément disponible dans la liste chaînée, puisque les ensembles sont des structures de données triées.

Dans le deuxième parcours de la liste chaînée, nous pouvons utiliser l'ensemble comme hachage. Nous rechercherons chaque élément de la collection, deux situations peuvent se présenter.

• Nous trouvons l'élément dans la collection, le supprimons de la collection et le marquons.

• Nous n'avons pas trouvé l'élément dans l'ensemble, ce qui signifie que nous l'avons déjà vu dans la première option et nous le remplacerons par le n suivant.

Exemple

Pour remplacer les nœuds par des valeurs en double dans une liste chaînée, veuillez suivre le programme C++ ci-dessous. L'implémentation C++ utilise une structure de données de collection pour parcourir la liste chaînée, facilitant ainsi la recherche d'éléments en double.

#include <iostream>
#include <set>
using namespace std;
class Node {
   public:
   int value;
   Node* next;
   Node(int value) {
      this->value = value;
      next = NULL;
   }
};
void solve(Node* head) {
   set<int> hash;
   Node* copy = head;
   while(copy) {
      hash.insert(copy->value);
      copy = copy->next;
   }
   auto it = hash.end();
   it--;
   int startingN = *it +1;
   while(head) {
      if(hash.find(head->value) != hash.end()) {
         hash.erase(head->value);
      } else {
         head->value = startingN++;
      }
      head = head->next;
   }
}
void printList(Node* head) {
   while(head) {
      cout << head->value << " ";
      head = head->next;
   }
}
int main() {
   Node* head = new Node(41);
   head->next = new Node(42);
   head->next->next = new Node(42);
   head->next->next->next = new Node(44);
   head->next->next->next->next = new Node(45);
   head->next->next->next->next->next = new Node(43);
   head->next->next->next->next->next->next = new Node(46);
   head->next->next->next->next->next->next->next = new Node(46);
   cout << "Before: ";
   printList(head);
   cout << "\n";
   solve(head);
   cout << "After: ";
   printList(head);
   return 0;
}

Sortie

Before: 41 42 42 44 45 43 46 46
After: 41 42 47 44 45 43 46 48  

Conclusion

Nous avons utilisé le concept de hachage et avons trouvé le plus grand élément de la liste chaînée à l'aide d'un ensemble de structures de données. Nous pouvons également utiliser map ou unordered_map comme hachage.

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!