verlinkte Liste: Dies ist eine verknüpfte Liste, die wir umkehren möchten.
Nach umgekehrter verknüpfter Liste: Das Folgende ist das Ergebnis nach Umkehrung der oben verlinkten Liste.
Im obigen Beispieldiagramm können wir sehen, dass der Kopfknoten und der Endknoten ihre Positionen ändern, wenn wir die verknüpfte Liste umkehren. Der Kopfknoten, der jetzt ein Schwanzknoten ist, zeigt auf den Nullknoten, weil er jetzt ein Schwanzknoten ist.
Algorithmusschritte
- Wir erstellen eine Hauptmethode und deklarieren einige erforderliche Variablen.
- Dann ist unser nächster Schritt, eine Methode zu erstellen, die eine verknüpfte Liste erstellen kann. Diese Methode hilft uns, eine verknüpfte Liste zu erstellen.
- Der nächste Schritt besteht darin, eine Methode zum Umkehren der verknüpften Liste zu erstellen. Bei dieser Methode übergeben wir die gesamte verknüpfte Liste, und diese Methode kehrt die verknüpfte Liste um.
- Jetzt brauchen wir eine andere Methode, um unser Ergebnis anzuzeigen, nachdem wir es umgekehrt haben.
- Wir werden alle diese oben genannten Methoden in unserer Hauptmethode kombinieren.
Wir werden die umgekehrte verkettete Liste anhand einer bildlichen Form erklären, um sie leichter verständlich zu machen. Beginnen wir also mit dem Beispiel.
Das Folgende ist eine verknüpfte Liste, die wir umkehren möchten.
Schritt 1 . Der grün gefärbte Knoten ist ein Kopfknoten, der auf den ersten Knoten im Startup zeigt.
Schritt 2. Im nächsten Schritt durchlaufen wir die gesamte verknüpfte Liste, bis wir den Nullzeiger neben dem Header-Knoten nicht mehr erhalten. Dazu weisen wir dem nächsten Knoten einen temporären Namen zu, wie im folgenden Diagramm gezeigt.
Schritt 3. Da wir einen neuen Referenzknoten namens „temporär“ haben, der uns helfen kann, die gesamte verknüpfte Liste zu durchlaufen, bis wir den Nullzeiger nicht erhalten, können wir den nächsten Link des Header-Knotens auf null setzen, was die Verknüpfung nicht beeinflusst Liste wie unten im Diagramm gezeigt. Der Nullzeiger neben dem aktuellen Knoten wird als vorheriger Knoten bezeichnet.
Schritt 4. Jetzt verschieben wir den temporären Knoten zum nächsten Knoten und den aktuellen Knoten zum vorherigen temporären Knoten. Jetzt sind wir also zum nächsten Knoten übergegangen. Wir ändern auch den vorherigen Knoten von null auf den vorherigen Knoten des aktuellen Knotens. Jetzt kümmert sich der temporäre Knoten um alle Traversen bis zum Nullzeiger, sodass wir den Link des aktuellen Knotens zum vorherigen Knoten setzen können, und jetzt zeigt er auf den vorherigen Knoten, wie im folgenden Diagramm gezeigt.
Wir folgen also den gleichen Schritten und erhalten schließlich eine umgekehrt verknüpfte Liste.
Schritt 5 .
Schritt 6.
Schritt 7.
Schritt 8.
Schritt 9.
Schritt 10.
Schritt 11.
Schritt 12.
Schritt 13.
Schritt 14. Bei diesem Schritt kehrte sich unsere verknüpfte Liste um.
C++ Programm zum Umkehren einer verketteten Liste
#includeverwenden Namensraum Standard ;
// Methode zum Erstellen des Knotens
Struktur Knoten {
int Wert ;
Knoten * nextNodePtr ;
} * nodeObject ;
Leere LinkedList erstellen ( int n ) ;
Leere reverseLinkedList ( Knoten ** nodeObject ) ;
Leere Anzeige ( ) ;
int hauptsächlich ( ) {
int n,wert,artikel ;
cout << 'Wie viele Knoten möchten Sie erstellen =>: ' ;
Essen >> n ;
LinkedList erstellen ( n ) ;
cout << ' \n Informationen in der verlinkten Liste: \n ' ;
Anzeige ( ) ;
cout << ' \n Verkettete Liste nach umgekehrt \n ' ;
reverseLinkedList ( & nodeObject ) ;
Anzeige ( ) ;
Rückkehr 0 ;
}
// Diese Methode erstellt die verknüpfte Liste
Leere LinkedList erstellen ( int n ) {
Struktur Knoten * frontNode, * tempNode ;
int Wert, d ;
nodeObject = ( Struktur Knoten * ) malloc ( Größe von ( Struktur Knoten ) ) ;
wenn ( nodeObject == NULL )
cout << 'Nicht genug, um das Gedächtnis zu bewerten' ;
anders {
cout << 'Bitte geben Sie die Informationen von Knoten 1 ein (nur Nummer): ' ;
Essen >> Wert ;
nodeObject - > Wert = Wert ;
nodeObject - > nextNodePtr = NULL ;
tempNode = nodeObject ;
zum ( ich = zwei ; ich <= n ; ich ++ ) {
frontNode = ( Struktur Knoten * ) malloc ( Größe von ( Struktur Knoten ) ) ;
// Wenn kein Knoten in der verknüpften Liste vorhanden ist
wenn ( frontNode == NULL ) {
cout << 'Speicher kann nicht zugewiesen werden' ;
Unterbrechung ;
}
anders {
cout << 'Bitte geben Sie die Informationen des Knotens ein' << ich << ':' ;
Essen >> Wert ;
frontNode - > Wert = Wert ;
frontNode - > nextNodePtr = NULL ;
tempNode - > nextNodePtr = frontNode ;
tempNode = tempNode - > nextNodePtr ;
}
}
}
}
Leere reverseLinkedList ( Knoten ** nodeObject ) {
Struktur Knoten * tempNode = NULL ;
Struktur Knoten * vorherigerKnoten = NULL ;
Struktur Knoten * aktueller Knoten = ( * nodeObject ) ;
während ( aktueller Knoten ! = NULL ) {
tempNode = aktueller Knoten - > nextNodePtr ;
aktueller Knoten - > nextNodePtr = vorherigerKnoten ;
vorherigerKnoten = aktueller Knoten ;
aktueller Knoten = tempNode ;
}
( * nodeObject ) = vorherigerKnoten ;
}
Leere Anzeige ( ) {
Struktur Knoten * tempNode ;
wenn ( nodeObject == NULL ) {
cout << 'Verknüpfte Liste ist leer' ;
}
anders {
tempNode = nodeObject ;
während ( tempNode ! = NULL )
{
cout << tempNode - > Wert << ' \t ' ;
tempNode = tempNode - > nextNodePtr ;
}
}
cout << Ende ;
}
Ausgabe
Wie viele Knoten möchten Sie erstellen =>: 6Bitte geben Sie die Informationen von Knoten 1 ein (nur Zahl): 101
Bitte geben Sie die Informationen von Knoten 2 ein: 95
Bitte geben Sie die Informationen von Knoten 3 ein: 61
Bitte geben Sie die Informationen von Knoten 4 ein: 19
Bitte geben Sie die Informationen von Knoten 5: 12 ein
Bitte geben Sie die Informationen von Knoten 6: 11 ein
Informationen in der verlinkten Liste:
101 95 61 19 12 11
Verkettete Liste nach umgekehrt
11 12 19 61 95 101
Fazit
Dieser LinuxHint-Artikel hat sich mit dem Umkehren einer verketteten Liste in C++ beschäftigt. Es gibt einige andere Methoden, um eine verkettete Liste umzukehren, aber dies ist eine sehr gebräuchliche Methode, um eine verkettete Liste umzukehren. Es liegt an Ihnen, zu entscheiden, wie Sie Ihre Probleme lösen möchten, aber im Allgemeinen sollte die umgekehrt verknüpfte Listenfunktion eine einfache Schleife mit Zeigertausch sein.