länkad lista: Det här är en länkad lista som vi vill vända.
Efter omvänd länkad lista: Nedanstående kommer att bli resultatet efter att den ovan länkade listan har vänts om.
I exemplet ovan kan vi se att huvudnoden och svansnoden ändrar sina positioner när vi vänder på den länkade listan. Huvudnoden, som nu är en svansnod, pekar på nollnoden eftersom den nu är en svansnod.
Algoritmsteg
- Vi skapar en huvudmetod och deklarerar några nödvändiga variabler.
- Sedan är vårt nästa steg att skapa en metod som kan skapa en länkad lista. Denna metod hjälper oss att skapa en länkad lista.
- Nästa steg är att skapa en metod för att vända den länkade listan. I den här metoden skickar vi hela den länkade listan, och den här metoden kommer att vända på den länkade listan.
- Nu behöver vi en annan metod för att visa vårt resultat efter att ha vänt det.
- Vi kommer att kombinera alla dessa ovanstående metoder i vår huvudmetod.
Vi kommer att förklara omvänd länkad lista med hjälp av någon bildform för att göra det lättare att förstå. Så låt oss börja med exemplet.
Nedan är en länkad lista som vi vill vända.
Steg 1 . Den grönfärgade noden är en huvudnod, som pekar på den första noden i uppstarten.
Steg 2. I nästa steg kommer vi att gå igenom hela den länkade listan tills vi inte får nollpekaren bredvid headernoden. För det kommer vi att tilldela nästa nod ett tillfälligt namn, som visas i diagrammet nedan.
Steg 3. Eftersom vi har en ny referensnod som heter 'temporary', som kan hjälpa oss att gå igenom hela den länkade listan tills vi inte får nollpekaren, så kan vi ställa in nästa länk i headernoden som null, vilket inte kommer att påverka den länkade lista som visas nedan i diagrammet. Nollpekaren bredvid den aktuella noden kallas föregående nod.
Steg 4. Nu flyttar vi den temporära noden till nästa nod och den nuvarande noden till den föregående temporära noden. Så nu har vi flyttat till nästa nod. Vi ändrar också den föregående noden från null till bara föregående nod för den nuvarande noden. Så nu kommer den temporära noden att ta hand om alla övergångar till nollpekaren så att vi kan ställa in länken för den nuvarande noden till den föregående noden, och nu pekar den på den föregående noden, som visas i diagrammet nedan.
Så vi följer samma steg och äntligen får vi en omvänd länkad lista.
Steg 5 .
Steg 6.
Steg 7.
Steg 8.
Steg 9.
Steg 10.
Steg 11.
Steg 12.
Steg 13.
Steg 14. I det här steget ändrades vår länkade lista.
C++ Program för att vända en länkad lista
#includeanvänder sig av namnutrymme std ;
// Metod för att skapa noden
struktur nod {
int värde ;
nod * nästaNodePtr ;
} * nodeObject ;
tomhet skapa länkad lista ( int n ) ;
tomhet reverseLinkedList ( nod ** nodeObject ) ;
tomhet visa ( ) ;
int huvud ( ) {
int n,värde,objekt ;
cout << 'Hur många noder vill du skapa =>: ' ;
äter >> n ;
skapa länkad lista ( n ) ;
cout << ' \n Information i den länkade listan: \n ' ;
visa ( ) ;
cout << ' \n Länkad lista efter omvänd \n ' ;
reverseLinkedList ( & nodeObject ) ;
visa ( ) ;
lämna tillbaka 0 ;
}
// Den här metoden skapar den länkade listan
tomhet skapa länkad lista ( int n ) {
struktur nod * frontNode, * tempNode ;
int värde, dvs ;
nodeObject = ( struktur nod * ) malloc ( storlek av ( struktur nod ) ) ;
om ( nodeObject == NULL )
cout << 'Inte tillräckligt för att få minne' ;
annan {
cout << 'Vänligen ange informationen för nod 1 (endast nummer): ' ;
äter >> värde ;
nodeObject - > värde = värde ;
nodeObject - > nästaNodePtr = NULL ;
tempNode = nodeObject ;
för ( i = två ; i <= n ; i ++ ) {
frontNode = ( struktur nod * ) malloc ( storlek av ( struktur nod ) ) ;
// När ingen nod i den länkade listan
om ( frontNode == NULL ) {
cout << 'Minnet kan inte allokeras' ;
ha sönder ;
}
annan {
cout << 'Vänligen ange information om nod' << i << ':' ;
äter >> värde ;
frontNode - > värde = värde ;
frontNode - > nästaNodePtr = NULL ;
tempNode - > nästaNodePtr = frontNode ;
tempNode = tempNode - > nästaNodePtr ;
}
}
}
}
tomhet reverseLinkedList ( nod ** nodeObject ) {
struktur nod * tempNode = NULL ;
struktur nod * föregående Nod = NULL ;
struktur nod * aktuell Nod = ( * nodeObject ) ;
medan ( aktuell Nod ! = NULL ) {
tempNode = aktuell Nod - > nästaNodePtr ;
aktuell Nod - > nästaNodePtr = föregående Nod ;
föregående Nod = aktuell Nod ;
aktuell Nod = tempNode ;
}
( * nodeObject ) = föregående Nod ;
}
tomhet visa ( ) {
struktur nod * tempNode ;
om ( nodeObject == NULL ) {
cout << 'Länkad lista är tom' ;
}
annan {
tempNode = nodeObject ;
medan ( tempNode ! = NULL )
{
cout << tempNode - > värde << ' \t ' ;
tempNode = tempNode - > nästaNodePtr ;
}
}
cout << endl ;
}
Produktion
Hur många noder vill du skapa =>: 6Vänligen ange informationen för nod 1 (endast nummer): 101
Vänligen ange informationen för nod 2: 95
Vänligen ange informationen för nod 3: 61
Vänligen ange informationen för nod 4:19
Vänligen ange informationen för nod 5: 12
Vänligen ange informationen för nod 6: 11
Information i den länkade listan:
101 95 61 19 12 11
Länkad lista efter omvänd
11 12 19 61 95 101
Slutsats
Den här LinuxHint-artikeln har granskat hur man vänder på en länkad lista i C++. Det finns några andra metoder för att vända en länkad lista, men detta är en mycket vanlig metod för att vända en länkad lista. Det är upp till dig att bestämma hur du vill lösa dina problem, men generellt bör den omvänd länkade listfunktionen vara en enkel loop med pekarbyten.