Supprimer le dernier nœud d'une liste chaînée en utilisant C++

Nous avons une liste chaînée unique et notre tâche est de supprimer le dernier nœud de cette liste chaînée. Dans ce problème, il nous suffit de parcourir la liste chaînée donnée et de simplement supprimer le dernier nœud.

Méthode pour trouver la solution

Dans cette méthode, nous parcourons la liste chaînée donnée et gardons une trace du nœud précédent et du nœud actuel. Lorsque notre nœud actuel devient le dernier nœud, nous changeons précédent -> à côté de NULL et supprimons le nœud actuel.

Exemple

#include <iostream>
using namespace std;

struct Node {
   int data;
   struct Node* next;
};
void push(struct Node** ref, int new_data) { // pushing the node
   struct Node* new_n = new Node;
   new_n->data = new_data;
   new_n->next = (*ref);
   (*ref) = new_n;
}
int main() {
   Node* head = NULL;
   push(&head, 12);
   push(&head, 29);
   push(&head, 11);
   push(&head, 23);
   push(&head, 8);
   auto curr = head, prev = head;
   if (!curr || !curr -> next) // if list only has one element or the list is empty
      cout << "Empty\n";
   else {
      while (curr) { // while curr != NULL
         if (!curr -> next) {
            prev -> next = NULL;
            delete(curr); // freeing the space
            break;
         }
         prev = curr;
         curr = curr -> next; // moving to the next node
      }
   }
   for (Node* temp = head; temp != NULL; temp = temp->next) // printing the data
      cout << temp->data << " ";

   return 0;
}

Sortie

8 23 11 29

Explication du code ci-dessus

Dans cette méthode, nous parcourons le tableau, en gardant une trace du nœud actuel et du nœud précédent. Lorsque le nœud actuel devient le dernier nœud, nous changeons précédent -> à côté de NULL et supprimons le nœud actuel. La complexité temporelle globale du programme donné est O(N), où N est la taille de la liste donnée.

Complexité temporelle - O(N)

N : taille d'un tableau donné

Conclusion

Dans cet article, nous avons résolu le problème de la suppression du dernier nœud d'une liste chaînée donnée. Nous avons également appris un programme C++ pour ce problème et notre approche complète pour le résoudre. Nous pouvons écrire le même programme dans d'autres langages comme C, Java, Python et d'autres langages. J'espère que cet article vous sera utile.

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!