Entfernen Sie Duplikate mithilfe der Rekursion aus einer sortierten verknüpften Liste

Eine verknüpfte Liste ist eine Folge von miteinander verbundenen Elementen. Jede Liste verfügt über einen Header und eine Folge von Knoten, von denen jeder Daten für den aktuellen Knoten enthält und mit dem nächsten Knoten verknüpft ist. Die Grundoperationen verknüpfter Listen sind Einfügen, Löschen, Suchen und Löschen.

Duplikate aus der sortierten verknüpften Liste entfernen

Eine Möglichkeit, Knoten zu löschen, ist die Verwendung der Rekursion. Die Idee besteht darin, jeden Knoten mit seinen Nachbarknoten zu vergleichen und doppelte Knoten zu entfernen, wenn sie gleich sind.

Unser rekursiver Aufruf kehrt zum nächsten Knoten zurück. Für das nächste Element rufen wir also die rekursive Funktion wie current_node->next = our_function(node->next) auf.

Wir vertrauen unserer Rekursion und current_node->next enthält jetzt die verknüpfte Liste ohne doppelte Elemente.

In der Hauptmethode bieten wir von Grund auf auf die Liste -

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

Algorithmus

Der Prozess der Verwendung der Rekursion zum Entfernen von Duplikaten aus einer sortierten verknüpften Liste ist wie folgt.

• Schritt 1 – Erstellen Sie eine verknüpfte Liste mit allen Werten in der richtigen Reihenfolge

• Schritt 2 – Wenn die verknüpfte Liste nicht existiert, wird das Programm beendet.

• Schritt 3 – Wenn die verknüpfte Liste vorhanden ist, vergleichen Sie den nächsten Wert des Kopfknotens mit dem Wert im Kopfknoten. Wenn beide Werte gleich sind, entfernen Sie die Kopfzeile.

• Schritt 4 – Schritt 3 wird rekursiv ausgeführt, jeden Knoten als Kopf behandeln, bis die Liste alle doppelten Werte aus sich selbst entfernt.

• Schritt 5 – Die erhaltene Ausgabe ist eine sortierte verknüpfte Liste mit verschiedenen Werten

Beispiel

Zum Beispiel haben wir eine sortierte verknüpfte Liste mit den folgenden Werten -

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

Sehen wir uns ein C++-Programm an, das Duplikate mithilfe der Rekursion aus der oben sortierten verknüpften Liste entfernt -

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

Danach prüfen wir, ob der aktuelle Knoten in der verknüpften Liste enthalten ist. Wenn die zufriedenstellende verknüpfte Liste, die wir vom aktuellen Knoten -> nächsten Knoten erhalten, denselben Wert wie dieser Knoten hat, schließen wir diesen Knoten nicht ein, andernfalls schließen wir ihn ein.

HINWEIS – Wenn der aktuelle Knoten NULL ist, geben wir die Grundbedingung der Rekursion zurück.

Ausgabe

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

Fazit

Wie wir beim rekursiven Aufruf gesehen haben, vertrauen wir darauf, dass der nächste Aufruf das erwartete Ergebnis des restlichen Problems erzielen wird. Wir haben gerade das aktuelle Teilproblem gelöst. Vor diesem Hintergrund prüfen wir, ob das aktuelle Element enthalten sein kann, und übergeben den Rest der verknüpften Liste an unseren rekursiven Aufruf, wobei wir darauf vertrauen, dass er uns von diesem Zeitpunkt an eine gültige verknüpfte Liste liefert. Wenn wir die gesamte verknüpfte Liste durchlaufen, beträgt die zeitliche Komplexität unserer Methode O(n).

Das obige ist der detaillierte Inhalt vonEntfernen Sie Duplikate mithilfe der Rekursion aus einer sortierten verknüpften Liste. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!