lista legata: Aceasta este o listă legată pe care dorim să o inversăm.
După lista legată inversă: Rezultatul de mai jos va fi după inversarea listei de mai sus.
În diagrama exemplu de mai sus, putem vedea că nodul cap și nodul de coadă își schimbă pozițiile atunci când inversăm lista legată. Nodul principal, care acum este un nod de coadă, indică nodul nul deoarece acum este un nod de coadă.
Etapele algoritmului
- Creăm o metodă principală și declarăm unele variabile necesare.
- Apoi, următorul nostru pas este să creăm o metodă care poate crea o listă legată. Această metodă ne ajută să creăm o listă legată.
- Următorul pas este să creați o metodă pentru a inversa lista legată. În această metodă, trecem întreaga listă legată, iar această metodă va inversa lista legată.
- Acum, avem nevoie de o altă metodă pentru a ne afișa rezultatul după ce îl inversăm.
- Vom combina toate aceste metode de mai sus în metoda noastră principală.
Vom explica lista inversată cu linkuri folosind o formă picturală pentru a o face mai ușor de înțeles. Deci, să începem cu exemplul.
Mai jos este o listă legată pe care dorim să o inversăm.
Pasul 1 . Nodul de culoare verde este un nod principal, care indică primul nod din pornire.
Pasul 2. În pasul următor, vom parcurge întreaga listă legată până când nu obținem indicatorul nul de lângă nodul antet. Pentru asta, vom atribui următorului nod un nume temporar, așa cum se arată în diagrama de mai jos.
Pasul 3. Deoarece avem un nou nod de referință numit „temporare”, care ne poate ajuta să traversăm întreaga listă legată până când nu obținem indicatorul nul, așa că putem seta următoarea legătură a nodului antet ca nul, ceea ce nu va afecta linkul. lista după cum se arată mai jos în diagramă. Pointerul nul de lângă nodul curent se numește nodul anterior.
Pasul 4. Acum, mutăm nodul temporar la următorul nod și nodul curent la nodul temporar anterior. Deci acum ne-am mutat la următorul nod. De asemenea, schimbăm nodul anterior din nul la doar nodul anterior al nodului curent. Deci, acum nodul temporar se va ocupa de toate traversările până la pointerul nul, astfel încât să putem seta legătura nodului curent cu nodul anterior, iar acum indică către nodul anterior, așa cum se arată în diagrama de mai jos.
Așa că urmam aceiași pași și, în cele din urmă, vom obține o listă inversată.
Pasul 5 .
Pasul 6.
Pasul 7.
Pasul 8.
Pasul 9.
Pasul 10.
Pasul 11.
Pasul 12.
Pasul 13.
Pasul 14. La acest pas, lista noastră legată s-a inversat.
Program C++ pentru a inversa o listă legată
#includefolosind spatiu de nume std ;
// Metoda de creare a nodului
struct nodul {
int valoare ;
nodul * nextNodePtr ;
} * nodeObject ;
gol createLinkedList ( int n ) ;
gol reverseLinkedList ( nodul ** nodeObject ) ;
gol afişa ( ) ;
int principal ( ) {
int n,valoare,articol ;
cout << „Câte noduri doriți să creați =>:” ;
mâncând >> n ;
createLinkedList ( n ) ;
cout << ' \n Informații din lista legată: \n ' ;
afişa ( ) ;
cout << ' \n Lista legată după inversare \n ' ;
reverseLinkedList ( & nodeObject ) ;
afişa ( ) ;
întoarcere 0 ;
}
// Această metodă va crea lista legată
gol createLinkedList ( int n ) {
struct nodul * frontNode, * tempNode ;
int valoare, i ;
nodeObject = ( struct nodul * ) malloc ( dimensiunea ( struct nodul ) ) ;
dacă ( nodeObject == NUL )
cout << „Nu este suficient pentru a evalua memoria” ;
altfel {
cout << „Vă rugăm să introduceți informațiile nodului 1 (numai numărul):” ;
mâncând >> valoare ;
nodeObject - > valoare = valoare ;
nodeObject - > nextNodePtr = NUL ;
tempNode = nodeObject ;
pentru ( i = Două ; i <= n ; i ++ ) {
frontNode = ( struct nodul * ) malloc ( dimensiunea ( struct nodul ) ) ;
// Când nu există niciun nod în lista legată
dacă ( frontNode == NUL ) {
cout << „Memoria nu poate fi alocată” ;
pauză ;
}
altfel {
cout << „Vă rugăm să introduceți informațiile nodului” << i << ':' ;
mâncând >> valoare ;
frontNode - > valoare = valoare ;
frontNode - > nextNodePtr = NUL ;
tempNode - > nextNodePtr = frontNode ;
tempNode = tempNode - > nextNodePtr ;
}
}
}
}
gol reverseLinkedList ( nodul ** nodeObject ) {
struct nodul * tempNode = NUL ;
struct nodul * previousNode = NUL ;
struct nodul * currentNode = ( * nodeObject ) ;
in timp ce ( currentNode ! = NUL ) {
tempNode = currentNode - > nextNodePtr ;
currentNode - > nextNodePtr = previousNode ;
previousNode = currentNode ;
currentNode = tempNode ;
}
( * nodeObject ) = previousNode ;
}
gol afişa ( ) {
struct nodul * tempNode ;
dacă ( nodeObject == NUL ) {
cout << „Lista de linkuri este goală” ;
}
altfel {
tempNode = nodeObject ;
in timp ce ( tempNode ! = NUL )
{
cout << tempNode - > valoare << ' \t ' ;
tempNode = tempNode - > nextNodePtr ;
}
}
cout << endl ;
}
Ieșire
Câte noduri doriți să creați =>: 6Vă rugăm să introduceți informațiile nodului 1 (numai numărul): 101
Vă rugăm să introduceți informațiile nodului 2: 95
Vă rugăm să introduceți informațiile nodului 3: 61
Vă rugăm să introduceți informațiile nodului 4: 19
Vă rugăm să introduceți informațiile nodului 5: 12
Vă rugăm să introduceți informațiile nodului 6: 11
Informații din lista legată:
101 95 61 19 12 11
Lista legată după inversare
11 12 19 61 95 101
Concluzie
Acest articol LinuxHint a analizat cum să inversați o listă legată în C++. Există și alte metode de a inversa o listă legată, dar aceasta este o metodă foarte comună de a inversa o listă legată. Depinde de dvs. să decideți cum doriți să vă rezolvați problemele, dar, în general, funcția de listă inversată ar trebui să fie o buclă simplă cu schimburi de pointer.