Maison > Article > développement back-end > 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
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.
Dans cette méthode, nous allons parcourir la liste chaînée et essayer de l'inverser pendant le parcours.
#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(); }
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.
Nous utiliserons une pile pour stocker tous les nœuds de ce programme et les inverserons en parcourant la pile.
#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(); }
85 15 4 20 20 4 15 85
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.
Dans cette méthode, nous effectuerons le même processus que précédemment mais en utilisant des appels récursifs.
#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(); }
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.
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!