Kehren Sie eine verknüpfte Liste mit C++ um

In diesem Artikel müssen wir den Link mithilfe einer einfach verknüpften Liste umkehren. Unsere Aufgabe besteht darin, eine Funktion zu erstellen, die eine gegebene einfach verknüpfte Liste umkehren kann. Zum Beispiel

Input:
Following Linked list :
1->2->3->4->NULL

Output:
After processing of our function:
4->3->2->1->NULL

Möglichkeiten, eine Lösung zu finden

Es gibt verschiedene Möglichkeiten, eine verknüpfte Liste umzukehren. Normalerweise denken wir an eine einfache Möglichkeit, die verknüpfte Liste beim Durchlaufen umzukehren.

Einfache Methode

Bei dieser Methode durchlaufen wir die verknüpfte Liste und versuchen, sie während des Durchlaufs umzukehren.

Beispiel

#include<bits/stdc++.h>
using namespace std;
struct Node {
   int data;
   struct Node* next;
   Node(int data) {
      this->data = data;
      next = NULL;
   }
};
struct LinkedList {
   Node* head;
   LinkedList() { head = NULL; }
   // Function to print linked list
   void reverse() {
      auto curr = head; // current pointer
      Node* prev = NULL; // previous pointer
      while(curr) {
         auto temp = curr -> next;
         curr -> next = prev;
         prev = curr;
         head = prev;
         curr = temp;
      }
   }
   void print() {
      struct Node* temp = head;
      while (temp != NULL) {
         cout << temp->data << " ";
         temp = temp->next;
      }
   }
   void push(int data) {
      Node* temp = new Node(data);
      temp->next = head;
      head = temp;
   }
};
int main() {
   LinkedList list;
   list.push(20);
   list.push(4);
   list.push(15);
   list.push(85);
   list.print();
   list.reverse();
   cout << "\n";
   list.print();
}

Ausgabe

85 15 4 20
20 4 15 85

Bei diesem Ansatz durchlaufen wir einfach die Liste und kehren sie während der Iteration um. Dies ist ein guter Ansatz, da die Zeitkomplexität O(N) beträgt, wobei N die Größe unserer Liste ist.

Jetzt versuchen wir ein Experiment durchzuführen und versuchen, die Liste mithilfe des Stapels umzukehren.

Methode mit Stapel

Wir werden einen Stapel verwenden, um alle Knoten in diesem Programm zu speichern und sie durch Durchlaufen des Stapels umzukehren.

Beispiel

#include<bits/stdc++.h>
using namespace std;
struct Node {
   int data;
   struct Node* next;
   Node(int data) {
      this->data = data;
      next = NULL;
   }
};
struct LinkedList {
   Node* head;
   LinkedList() { head = NULL; }
   // Function to print linked list
   void reverse() {
      auto curr = head; // current pointer
      Node* prev = NULL; // previous pointer
      stack<Node *> s;
      while(curr) {
         s.push(curr);
         curr = curr -> next;
      }
      prev = s.top();
      head = prev;
      s.pop();
      while(!s.empty()) {
         auto temp = s.top();
         s.pop();
         prev -> next = temp;
         prev = temp;
      }
      prev -> next = NULL;
   }
   void print() {
      struct Node* temp = head;
      while (temp != NULL) {
         cout << temp->data << " ";
         temp = temp->next;
      }
   }
   void push(int data) {
      Node* temp = new Node(data);
      temp->next = head;
      head = temp;
   }
};
int main() {
   LinkedList list;
   list.push(20);
   list.push(4);
   list.push(15);
   list.push(85);
   list.print();
   list.reverse();
   cout << "\n";
   list.print();
}

Ausgabe

85 15 4 20
20 4 15 85

Erläuterung des obigen Codes

Bei diesem Ansatz speichern wir die Listenknoten im Stapel, während wir die Liste durchlaufen, und verwenden dann den Stapel, um sie zu platzieren und die Liste umzukehren Ansatz Die Zeitkomplexität ist ebenfalls O(N), wobei N die Größe unserer Liste ist. Wie zuvor haben wir den Stapel verwendet, daher können wir auch die rekursive Methode verwenden, da die Rekursion auch den Stapel verwendet, und jetzt werden wir die rekursive Methode verwenden.

Rekursive Methode

In dieser Methode führen wir den gleichen Prozess wie zuvor durch, verwenden jedoch rekursive Aufrufe.

Beispiel

#include<bits/stdc++.h>
using namespace std;
struct Node {
   int data;
   struct Node* next;
   Node(int data) {
      this->data = data;
      next = NULL;
      }
   };
   struct LinkedList {
      Node* head;
      LinkedList() { head = NULL; }
      // Function to print linked list
      void rreverse(Node *curr, Node *prev) {
         if(curr == NULL) {
            // prev -> next = curr;
            head = prev;
            return;
         }
         rreverse(curr -> next, curr);
         curr -> next = prev;
         prev -> next = NULL;
      }

      void reverse() {
         auto curr = head; // current pointer
         Node* prev = NULL; // previous pointer
         rreverse(curr -> next, curr);
      }
      void print() {
         struct Node* temp = head;
         while (temp != NULL) {
         cout << temp->data << " ";
         temp = temp->next;
      }
   }
   void push(int data) {
      Node* temp = new Node(data);
      temp->next = head;
      head = temp;
   }
};
int main() {
   LinkedList list;
   list.push(20);
   list.push(4);
   list.push(15);
   list.push(85);
   list.print();
   list.reverse();
   cout << "\n";
   list.print();
}

Ausgabe

85 15 4 20
20 4 15 85

Bei diesem Ansatz machen wir dasselbe wie zuvor, verwenden jedoch rekursive Aufrufe, sodass die zeitliche Komplexität dieses Ansatzes ebenfalls O(N) beträgt, wobei N die Größe unserer Liste ist.

Fazit

In diesem Artikel haben wir das Problem der Umkehrung einer einfach verknüpften Liste gelöst. Wir haben auch das C++-Programm und die vollständige Methode (normale Methode und zwei weitere Methoden) gelernt, um dieses Problem zu lösen. Wir können das gleiche Programm in anderen Sprachen wie C, Java, Python und anderen schreiben. Ich hoffe, Sie finden diesen Artikel hilfreich.

Das obige ist der detaillierte Inhalt vonKehren Sie eine verknüpfte Liste mit C++ um. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!