lista collegata: Questo è un elenco collegato che vogliamo invertire.
Dopo l'elenco collegato invertito: Quanto segue sarà il risultato dopo aver invertito l'elenco sopra collegato.
Nel diagramma di esempio sopra, possiamo vedere che il nodo di testa e il nodo di coda cambiano le loro posizioni quando invertiamo l'elenco collegato. Il nodo di testa, che ora è un nodo di coda, punta al nodo nullo perché ora è un nodo di coda.
Passaggi dell'algoritmo
- Creiamo un metodo principale e dichiariamo alcune variabili obbligatorie.
- Quindi, il passaggio successivo consiste nel creare un metodo in grado di creare un elenco collegato. Questo metodo ci aiuta a creare un elenco collegato.
- Il passaggio successivo consiste nel creare un metodo per invertire l'elenco collegato. In questo metodo, passiamo l'intero elenco collegato e questo metodo invertirà l'elenco collegato.
- Ora, abbiamo bisogno di un altro metodo per visualizzare il nostro risultato dopo averlo invertito.
- Combineremo tutti questi metodi di cui sopra nel nostro metodo principale.
Spiegheremo l'elenco di collegamenti invertiti utilizzando una forma pittorica per renderlo più facile da capire. Quindi iniziamo con l'esempio.
Quello che segue è un elenco collegato che vogliamo invertire.
Passo 1 . Il nodo di colore verde è un nodo principale, che punta al primo nodo nell'avvio.
Passo 2. Nel passaggio successivo, attraverseremo l'intero elenco collegato fino a quando non otterremo il puntatore nullo accanto al nodo dell'intestazione. Per questo, assegneremo al nodo successivo un nome temporaneo, come mostrato nel diagramma sottostante.
Passaggio 3. Poiché abbiamo un nuovo nodo di riferimento denominato 'temporaneo', che può aiutarci a percorrere l'intero elenco collegato fino a quando non otteniamo il puntatore nullo, possiamo impostare il collegamento successivo del nodo dell'intestazione come nullo, che non influirà sul collegamento elenco come mostrato di seguito nel diagramma. Il puntatore null accanto al nodo corrente è chiamato nodo precedente.
Passaggio 4. Ora spostiamo il nodo temporaneo al nodo successivo e il nodo corrente al nodo temporaneo precedente. Quindi ora siamo passati al nodo successivo. Modifichiamo anche il nodo precedente da null al solo nodo precedente del nodo corrente. Quindi ora il nodo temporaneo si occuperà di tutte le traverse fino al puntatore nullo in modo che possiamo impostare il collegamento del nodo corrente al nodo precedente, e ora punta al nodo precedente, come mostrato nel diagramma sottostante.
Quindi seguiamo gli stessi passaggi e, alla fine, otterremo un elenco di collegamenti invertiti.
Passaggio 5 .
Passaggio 6.
Passaggio 7.
Passaggio 8.
Passaggio 9.
Passo 10.
Passaggio 11.
Passo 12.
Passo 13.
Passaggio 14. A questo punto, il nostro elenco collegato si è invertito.
Programma C++ per invertire un elenco collegato
#includeutilizzando spazio dei nomi standard ;
// Metodo per creare il nodo
struct nodo {
int valore ;
nodo * nextNodePtr ;
} * nodoOggetto ;
vuoto createLinkedList ( int n ) ;
vuoto reverseLinkedList ( nodo ** nodoOggetto ) ;
vuoto Schermo ( ) ;
int principale ( ) {
int n,valore,oggetto ;
cout << 'Quanti nodi vuoi creare =>: ' ;
mangiare >> n ;
createLinkedList ( n ) ;
cout << ' \n Informazioni nell'elenco collegato: \n ' ;
Schermo ( ) ;
cout << ' \n Elenco collegato dopo l'inversione \n ' ;
reverseLinkedList ( & nodoOggetto ) ;
Schermo ( ) ;
Restituzione 0 ;
}
// Questo metodo creerà l'elenco collegato
vuoto createLinkedList ( int n ) {
struct nodo * frontNode, * tempNode ;
int valore, I ;
nodoOggetto = ( struct nodo * ) malloc ( taglia di ( struct nodo ) ) ;
Se ( nodoOggetto == NULLO )
cout << 'Non abbastanza per assaggiare la memoria' ;
altro {
cout << 'Inserisci le informazioni del nodo 1 (solo numero): ' ;
mangiare >> valore ;
nodoOggetto - > valore = valore ;
nodoOggetto - > nextNodePtr = NULLO ;
tempNode = nodoOggetto ;
per ( io = Due ; io <= n ; io ++ ) {
frontNode = ( struct nodo * ) malloc ( taglia di ( struct nodo ) ) ;
// Quando nessun nodo nell'elenco collegato
Se ( frontNode == NULLO ) {
cout << 'La memoria non può essere assegnata' ;
rompere ;
}
altro {
cout << 'Inserisci le informazioni del nodo' << io << ':' ;
mangiare >> valore ;
frontNode - > valore = valore ;
frontNode - > nextNodePtr = NULLO ;
tempNode - > nextNodePtr = frontNode ;
tempNode = tempNode - > nextNodePtr ;
}
}
}
}
vuoto reverseLinkedList ( nodo ** nodoOggetto ) {
struct nodo * tempNode = NULLO ;
struct nodo * precedenteNode = NULLO ;
struct nodo * currentNode = ( * nodoOggetto ) ;
mentre ( currentNode ! = NULLO ) {
tempNode = currentNode - > nextNodePtr ;
currentNode - > nextNodePtr = precedenteNode ;
precedenteNode = currentNode ;
currentNode = tempNode ;
}
( * nodoOggetto ) = precedenteNode ;
}
vuoto Schermo ( ) {
struct nodo * tempNode ;
Se ( nodoOggetto == NULLO ) {
cout << 'Lista collegata è vuota' ;
}
altro {
tempNode = nodoOggetto ;
mentre ( tempNode ! = NULLO )
{
cout << tempNode - > valore << ' \t ' ;
tempNode = tempNode - > nextNodePtr ;
}
}
cout << finel ;
}
Produzione
Quanti nodi vuoi creare =>: 6Inserisci le informazioni del nodo 1 (solo numero): 101
Inserisci le informazioni del nodo 2: 95
Inserisci le informazioni del nodo 3: 61
Inserisci le informazioni del nodo 4: 19
Inserisci le informazioni del nodo 5: 12
Inserisci le informazioni del nodo 6: 11
Informazioni nell'elenco collegato:
101 95 61 19 12 11
Elenco collegato dopo l'inversione
11 12 19 61 95 101
Conclusione
Questo articolo di LinuxHint ha esaminato come invertire un elenco collegato in C++. Esistono altri metodi per invertire un elenco collegato, ma questo è un metodo molto comune per invertire un elenco collegato. Spetta a te decidere come vuoi risolvere i tuoi problemi, ma generalmente la funzione di elenco concatenato inverso dovrebbe essere un semplice ciclo con scambi di puntatori.