Löschen Sie den letzten Knoten einer verknüpften Liste mit C++

Wir haben eine einfach verknüpfte Liste und unsere Aufgabe besteht darin, den letzten Knoten aus dieser verknüpften Liste zu löschen. Bei diesem Problem müssen wir nur die angegebene verknüpfte Liste durchlaufen und einfach den letzten Knoten löschen.

Methode zum Finden der Lösung

Bei dieser Methode durchlaufen wir die gegebene verknüpfte Liste und verfolgen den vorherigen und den aktuellen Knoten. Wenn unser aktueller Knoten der letzte Knoten wird, ändern wir previous -> next zu NULL und löschen den aktuellen Knoten.

Beispiel

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

Ausgabe

8 23 11 29

Erklärung des obigen Codes

Bei dieser Methode iterieren wir durch das Array und verfolgen dabei den aktuellen Knoten und den vorherigen Knoten. Wenn der aktuelle Knoten der letzte Knoten wird, ändern wir previous -> next auf NULL und löschen den aktuellen Knoten. Die Gesamtzeitkomplexität des gegebenen Programms beträgt O(N), wobei N die Größe der gegebenen Liste ist.

Zeitkomplexität – O(N)

N: Größe des gegebenen Arrays

Fazit

In diesem Artikel haben wir das Problem gelöst, den letzten Knoten aus einer gegebenen verknüpften Liste zu entfernen. Wir haben auch ein C++-Programm für dieses Problem und unseren vollständigen Lösungsansatz kennengelernt. Wir können das gleiche Programm in anderen Sprachen wie C, Java, Python und anderen Sprachen schreiben. Ich hoffe, Sie finden diesen Artikel hilfreich.

Das obige ist der detaillierte Inhalt vonLöschen Sie den letzten Knoten einer verknüpften Liste mit C++. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!