Inverser une liste doublement chaînée en utilisant C++

Dans cet article nous avons une liste doublement chaînée et nous expliquerons les différentes manières d'inverser une liste doublement chaînée en C++. Par exemple -

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

Habituellement, une méthode nous vient à l'esprit, mais nous utiliserons deux méthodes - la méthode normale et la méthode peu orthodoxe.

Méthode normale

Dans cette méthode, nous allons parcourir la liste et au fur et à mesure que nous la parcourons, nous l'inversons.

Exemple

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

Sortie

Before
9 8 4 6
After
6 4 8 9

Cette approche nécessite O(N)complexité temporelle, ce qui est très bien car cette complexité peut être réalisée sous des contraintes plus élevées.

Méthode peu orthodoxe

Comme son nom l'indique, ce n'est pas une méthode très courante à laquelle les utilisateurs pensent, mais nous explorerons également cette méthode. Dans cette approche, nous allons créer une pile et continuer à y insérer des données et, lors de la pop, nous modifierons sa valeur.

Exemple

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

Sortie

Before
9 8 4 6
After
6 4 8 9

Explication du code ci-dessus

Dans cette approche, nous utilisons une pile, remplissons la pile tout en parcourant la liste, puis retirons les éléments de la pile et modifions leurs valeurs pour que la liste C'est le contraire. O(N) est la complexité temporelle de ce programme, qui s'applique également aux contraintes plus élevées.

Conclusion

Dans cet article, nous avons résolu un problème d'inversion d'une liste doublement chaînée avec ou sans pile. La complexité temporelle est O(N), où N est la taille de la liste. Nous avons également appris un programme C++ pour résoudre ce problème et des méthodes complètes (normales et peu orthodoxes) pour résoudre ce problème. Nous pouvons écrire le même programme dans d'autres langages tels que C, Java, Python et d'autres langages. Nous espérons que cet article vous a été 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!