Inverser une liste liée

Comment inverser une liste liée en C ++ est montrée dans ce tutoriel LinuxHint. Lorsque vous inversez une liste liée, le chemin du lien est inversé et la tête devient la queue, et la queue devient la tête. En échangeant les positions des nœuds, nous pouvons comprendre cela rapidement. Dans cet échange, nous changeons simplement les positions des nœuds de gauche à droite ou vice-versa.

Liste liée: Ceci est une liste liée que nous voulons inverser.

Après la liste liée inversée: Ce qui précède sera le résultat après avoir inversé la liste liée ci-dessus.

Dans l'exemple ci-dessus, nous pouvons voir que le nœud de tête et le nœud de queue modifient leurs positions lorsque nous inversons la liste liée. Le nœud de tête, qui est maintenant un nœud de queue, pointe vers le nœud nul car il s'agit maintenant d'un nœud de queue.

Étapes d'algorithme

1. Nous créons une méthode principale et déclarons certaines variables requises.
2. Ensuite, notre prochaine étape consiste à créer une méthode qui peut créer une liste liée. Cette méthode nous aide à créer une liste liée.
3. L'étape suivante consiste à créer une méthode pour inverser la liste liée. Dans cette méthode, nous passons toute la liste liée, et cette méthode inversera la liste liée.
4. Maintenant, nous avons besoin d'une autre méthode pour afficher notre résultat après l'avoir inversé.
5. Nous combinerons toutes ces méthodes ci-dessus dans notre méthode principale.

Nous allons expliquer la liste liée inversée en utilisant un formulaire pictural pour le rendre plus facile à comprendre. Alors commençons par l'exemple.

Ci-dessous est une liste liée que nous voulons inverser.

Étape 1. Le nœud de couleur verte est un nœud de tête, qui pointe vers le premier nœud du démarrage.

Étape 2. Dans l'étape suivante, nous traverserons toute la liste liée jusqu'à ce que nous n'obtenons pas le pointeur nul à côté du nœud d'en-tête. Pour cela, nous allons attribuer au nœud suivant un nom temporaire, comme indiqué dans le diagramme ci-dessous.

Étape 3. Comme nous avons un nouveau nœud de référence nommé «Temporary», qui peut nous aider à traverser toute la liste liée jusqu'à ce que nous n'obtenions pas le pointeur nul, afin que nous puissions définir le lien suivant du nœud d'en-tête comme nul, ce qui n'affectera pas le lien Liste comme indiqué ci-dessous dans le diagramme. Le pointeur nul à côté du nœud actuel est appelé le nœud précédent.

Étape 4. Maintenant, nous déplaçons le nœud temporaire vers le nœud suivant et le nœud actuel vers le nœud temporaire précédent. Alors maintenant, nous sommes passés au nœud suivant. Nous modifions également le nœud précédent de NULL au nœud précédent du nœud actuel. Alors maintenant, le nœud temporaire s'occupera de toutes les traversées jusqu'au pointeur nul afin que nous puissions définir le lien du nœud actuel au nœud précédent, et maintenant il pointe vers le nœud précédent, comme indiqué dans le diagramme ci-dessous.

Nous suivons donc les mêmes étapes et, enfin, nous obtiendrons une liste liée inversée.

Étape 5.

Étape 6.

Étape 7.

Étape 8.

Étape 9.

Étape 10.

Étape 11.

Étape 12.

Étape 13.

Étape 14. À cette étape, notre liste liée a inversé.

Programme C ++ pour inverser une liste liée

#inclure
Utilisation de Namespace Std;
// Méthode pour créer le nœud
nœud struct
INT VALEUR;
nœud * nextNodePtr;
* nodeObject;
void CreateLlinkEdList (int n);
void reverselinkedList (Node ** nodeObject);
void disposer ();
int main()
int n, valeur, élément;
couter<<"How many nodes you want to create =>: ";
cin >> n;
CreateLinkedList (n);
couter<<"\nInformation in the linked list: \n";
afficher();
couter<<"\nLinked list after reversed\n";
reverselinkedList (& nodeObject);
afficher();
retour 0;

// Cette méthode créera la liste liée
void createLlinkedList (int n)
Node de structure * FrontNode, * tempnode;
INT VALEUR, I;
NodeObject = (struct nœud *) malloc (sizeof (struct nœud));
if (nodeObject == null)
couter<<" Not enough to assing memory";
autre
couter<<"Please enter the info of node 1 (number only): ";
cin >> valeur;
nodeObject-> value = value;
nodeObject-> nextNodePtr = null;
tempnode = nodeObject;
pour (i = 2; i<=n; i++)
FrontNode = (nœud struct *) malloc (sizeof (nœud struct));
// quand aucun nœud dans la liste liée
if (frontnode == null)
couter<<"Memory can not be allocated";
casser;

autre
couter<<"Please enter the info of node "<cin >> valeur;
FrontNode-> valeur = valeur;
FrontNode-> nextNodePtr = null;
tempnode-> nextNodePtr = FrontNode;
tempnode = tempnode-> nextNodePtr;




void reverselinkedList (node ​​** nodeObject)
struct nœud * tempnode = null;
struct nœud * PREVERNODE = NULL;
struct node * currentNode = (* nodeObject);
Pendant (courant de courant != Null)
tempnode = currentNode-> nextNodePtr;
currentNode-> nextNodePtr = PREVERNODE;
PREBERNODE = COURTHNODE;
currentNode = tempNode;

(* NodeObject) = PREVERNODE;

void display ()
nœud struct * tempnode;
if (nodeObject == null)
couter<<"Linkedlist is empty";

autre
tempnode = nodeObject;
pendant (tempnode != Null)

couter<valeur<<"\t";
tempnode = tempnode-> nextNodePtr;


couter <

Sortir

Combien de nœuds souhaitez-vous créer =>: 6
Veuillez saisir les informations du nœud 1 (numéro uniquement): 101
Veuillez saisir les informations du nœud 2: 95
Veuillez saisir les informations du nœud 3: 61
Veuillez saisir les informations du nœud 4: 19
Veuillez saisir les informations du nœud 5: 12
Veuillez saisir les informations du nœud 6: 11
Informations dans la liste liée:
101 95 61 19 12 11
Liste liée après inversion
11 12 19 61 95 101

Conclusion

Cet article de Linuxhint a examiné comment inverser une liste liée en C++. Il existe d'autres méthodes pour inverser une liste liée, mais il s'agit d'une méthode très courante pour inverser une liste liée. C'est à vous de décider comment vous souhaitez résoudre vos problèmes, mais généralement la fonction de liste liée inverse devrait être une boucle simple avec des échanges de pointeurs.