Supprimer les doublons de la liste chaînée triée à l'aide de la récursivité

Une liste chaînée est une séquence d'éléments connectés entre eux. Chaque liste comporte un en-tête et une série de nœuds, chacun contenant des données pour le nœud actuel et des liens vers le nœud suivant. Les opérations de base des listes chaînées sont l'insertion, la suppression, la recherche et la suppression.

Supprimer les doublons de la liste chaînée triée

Une façon de supprimer des nœuds consiste à utiliser la récursivité. L'idée est de comparer chaque nœud avec ses nœuds voisins et de supprimer les nœuds en double là où ils sont égaux.

Notre appel récursif reviendra au nœud suivant. Donc pour l'élément suivant, nous appellerons la fonction récursive comme current_node->next = our_function(node->next).

Nous faisons confiance à notre récursivité et current_node->next contient désormais la liste chaînée sans aucun élément en double.

Dans la méthode principale, nous enchérissons sur la liste à partir de zéro -

Node* head = new Node(5);
head->next = new Node(5);
head->next->next = new Node(6);
head->next->next->next = new Node(7);
head->next->next->next->next = new Node(7);
head->next->next->next->next->next = new Node(7); 

Algorithme

Le processus d'utilisation de la récursivité pour supprimer les doublons d'une liste chaînée triée est le suivant.

• Étape 1 - Créez une liste chaînée avec toutes les valeurs triées dans l'ordre

• Étape 2 - Si la liste chaînée n'existe pas, le programme se termine.

• Étape 3 - Si la liste chaînée existe, comparez la valeur suivante du nœud principal avec la valeur du nœud principal. Si les deux valeurs sont identiques, supprimez l'en-tête.

• Étape 4 - L'étape 3 est effectuée de manière récursive, traitant chaque nœud comme une tête jusqu'à ce que la liste supprime toutes les valeurs en double d'elle-même.

• Étape 5 - Le résultat obtenu est une liste chaînée triée avec différentes valeurs

Exemple

Par exemple, nous avons une liste chaînée triée avec les valeurs suivantes -

1->1->1->2->3->3->4

Voyons un programme C++ qui supprimera les doublons de la liste chaînée triée ci-dessus en utilisant la récursivité -

#include <iostream>
using namespace std;
class Node {
   public:
   int data;
   Node* next;
   Node(int data) {
   this->data = data;
   next = NULL;
   }
};
Node* solve(Node* head) {
   if (head == NULL)
   return NULL;
   head->next = solve(head->next);
   if (head->next != NULL && head->next->data == head->data) {
      Node* temp = head->next;
      delete head;
      return temp;
   }
   return head;
}
void printList(Node* node) {
   while (node != NULL) {
      cout << node->data << (node->next == NULL ? "" : "->");
      node = node->next;
   }
}
int main() {
   Node* head = new Node(1);
   head->next = new Node(1);
   head->next->next = new Node(1);
   head->next->next->next = new Node(2);
   head->next->next->next->next = new Node(3);
   head->next->next->next->next->next = new Node(3);
   head->next->next->next->next->next->next = new Node(4);
   cout << "Linked list before: ";
   printList(head);
   head = solve(head);
   cout << "\nLinked list after: ";
   printList(head);
   return 0;
}

Après cela, nous vérifions si le nœud actuel est inclus dans la liste chaînée. Si la liste chaînée satisfaisante que nous obtenons du nœud actuel -> nœud suivant a la même valeur que ce nœud, nous n'incluons pas ce nœud sinon, nous l'incluons ;

REMARQUE - Lorsque le nœud actuel est NULL, nous renvoyons la condition de base de la récursivité.

Sortie

Linked list before: 1->1->1->2->3->3->4
Linked list after: 1->2->3->4

Conclusion

Comme nous l'avons vu avec l'appel récursif, nous sommes convaincus que le prochain appel atteindra le résultat attendu du reste du problème. Nous venons de résoudre le sous-problème actuel. Dans cet esprit, nous vérifions si l'élément actuel peut être contenu et remettons le reste de la liste chaînée à notre appel récursif, en lui faisant confiance pour nous donner une liste chaînée valide à partir de ce moment. Lorsque nous parcourons toute la liste chaînée, la complexité temporelle de notre méthode est O(n).

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!