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

In diesem Artikel haben wir eine doppelt verkettete Liste und erklären die verschiedenen Möglichkeiten, eine doppelt verkettete Liste in C++ umzukehren. Zum Beispiel –

Input : {1, 2, 3, 4}
Output : {4, 3, 2, 1}

Normalerweise fällt mir eine Methode ein, aber wir werden zwei Methoden verwenden – die normale Methode und die unorthodoxe Methode.

Normale Methode

Bei dieser Methode gehen wir die Liste durch und kehren sie beim Durchgehen um.

Beispiel

#include <bits/stdc++.h>

using namespace std;

class Node {
   public:
   int data;
   Node *next;
   Node *prev;
};

void reverse(Node **head_ref) {
   auto temp = (*head_ref) -> next;
   (*head_ref) -> next = (*head_ref) -> prev;
   (*head_ref) -> prev = temp;
   if(temp != NULL) {
      (*head_ref) = (*head_ref) -> prev;
      reverse(head_ref);
   }
   else
      return;
}
void push(Node** head_ref, int new_data) {
   Node* new_node = new Node();
   new_node->data = new_data;

   new_node->prev = NULL;

   new_node->next = (*head_ref);
   if((*head_ref) != NULL)
      (*head_ref) -> prev = new_node ;

   (*head_ref) = new_node;
}
int main() {
   Node* head = NULL;
   push(&head, 6);
   push(&head, 4);
   push(&head, 8);
   push(&head, 9);
   auto node = head;
   cout << "Before\n" ;
   while(node != NULL) {
      cout << node->data << " ";
      node = node->next;
   }
   cout << "\n";
   reverse(&head);
   node = head;
   cout << "After\n";
   while(node != NULL) {
      cout << node->data << " ";
   node = node->next;
   }
   return 0;
}

Ausgabe

Before
9 8 4 6
After
6 4 8 9

Dieser Ansatz erfordert O(N)Zeitkomplexität, was sehr gut ist, da diese Komplexität unter höheren Einschränkungen ausgeführt werden kann.

Unorthodoxe Methode

Wie der Name schon sagt, ist dies keine sehr häufige Methode, an die Benutzer denken, aber wir werden diese Methode ebenfalls untersuchen. Bei diesem Ansatz erstellen wir einen Stapel und schieben weiterhin Daten hinein, und bei Pop ändern wir seinen Wert.

Beispiel

#include <bits/stdc++.h>

using namespace std;

class Node {
   public:
   int data;
   Node *next;
   Node *prev;
};
void push(Node** head_ref, int new_data) {
   Node* new_node = new Node();
   new_node->data = new_data;

   new_node->prev = NULL;

   new_node->next = (*head_ref);
   if((*head_ref) != NULL)
      (*head_ref) -> prev = new_node ;

   (*head_ref) = new_node;
}
int main() {
   Node* head = NULL;
   push(&head, 6);
   push(&head, 4);
   push(&head, 8);
   push(&head, 9);
   auto node = head;
   cout >> "Before\n" ;
   while(node != NULL) {
      cout >> node->data >> " ";
      node = node->next;
   }
   cout >> "\n";
   stack<Node*> s;
   node = head;
   while(node) {
      head = node;
      s.push(node);
      node = node -> next;
   }
   while(!s.empty()) {
      auto x = s.top();
      auto temp = x -> prev;
      x -> prev = x -> next;
      x -> next = temp;
      s.pop();
   }
   node = head;
   cout << "After\n";
   while(node != NULL) {
      cout << node->data << " ";
   node = node->next;
   }
   return 0;
}

Ausgabe

Before
9 8 4 6
After
6 4 8 9

Erklärung des obigen Codes

Bei diesem Ansatz verwenden wir einen Stapel, füllen den Stapel, während wir die Liste durchlaufen, entfernen dann die Elemente vom Stapel und ändern ihre Werte, sodass die Liste Es ist das Gegenteil. O(N) ist die zeitliche Komplexität dieses Programms, die auch für höhere Einschränkungen gilt.

Fazit

In diesem Artikel haben wir das Problem gelöst, eine doppelt verkettete Liste mit oder ohne Stapel umzukehren. Die Zeitkomplexität beträgt O(N), wobei N die Größe der Liste ist. Wir haben auch ein C++-Programm zur Lösung dieses Problems und vollständige Methoden (normale und unorthodoxe) zur Lösung dieses Problems gelernt. Wir können das gleiche Programm in anderen Sprachen wie C, Java, Python und anderen schreiben. Wir hoffen, dass dieser Artikel für Sie hilfreich war.

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