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

Dans cet article, nous devons inverser le lien à l'aide d'une liste à chaînage unique. Notre tâche est de créer une fonction capable d'inverser une liste à chaînage unique donnée. Par exemple

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

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

Façons de trouver une solution

Il existe différentes manières d'inverser une liste chaînée. Habituellement, nous pensons à un moyen simple d’inverser la liste chaînée tout en la parcourant.

Méthode facile

Dans cette méthode, nous allons parcourir la liste chaînée et essayer de l'inverser pendant le parcours.

Exemple

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

Sortie

85 15 4 20
20 4 15 85

Dans cette approche, nous parcourons simplement la liste et l'inversons au cours de l'itération. C'est une bonne approche car la complexité temporelle est O(N), où N est la taille de notre liste.

Maintenant, nous essayons de faire une expérience et d'inverser la liste en utilisant la pile.

Méthode utilisant la pile

Nous utiliserons une pile pour stocker tous les nœuds de ce programme et les inverserons en parcourant la pile.

Exemple

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

Sortie

85 15 4 20
20 4 15 85

Explication du code ci-dessus

Dans cette approche, nous stockons les nœuds de liste dans la pile tout en parcourant la liste, puis utilisons la pile pour les afficher et inverser le but de cette opération ; approche La complexité temporelle est également O(N), où N est la taille de notre liste. Comme auparavant, nous avons utilisé la pile, nous pouvons donc également utiliser la méthode récursive, car la récursion utilise également la pile, et maintenant nous allons utiliser la méthode récursive.

Méthode récursive

Dans cette méthode, nous effectuerons le même processus que précédemment mais en utilisant des appels récursifs.

Exemple

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

Output

85 15 4 20
20 4 15 85

Dans cette approche, nous faisons la même chose qu'avant mais en utilisant des appels récursifs, donc la complexité temporelle de cette approche est également O(N), où N est la taille de notre liste.

Conclusion

Dans cet article, nous avons résolu le problème de l'inversion d'une liste à chaînage unique. Nous avons également appris le programme C++ et la méthode complète (méthode normale et deux autres méthodes) pour résoudre ce problème. Nous pouvons écrire le même programme dans d'autres langages comme C, Java, Python et autres. J'espère que cet article vous sera 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!