Come invertire una lista unica Linked

April 9

Come invertire una lista unica Linked


E 'comune per necessità di invertire una lista collegata, ma può essere difficile da fare in modo corretto. Una delle soluzioni più semplici è quello di scorrere attraverso il ciclo, invertendo ogni puntatore. Questo pseudocodice mostra come eseguire questo processo tenendo traccia delle variabili necessarie. Il pseudocodice è sufficientemente generico che si dovrebbe essere in grado di adattarsi a qualsiasi lingua il codice è in.

istruzione

1 Verificare la presenza di semplici casi limite. Se il puntatore di testa è nullo, l'elenco è vuoto e nessun lavoro deve essere fatto. Se il prossimo puntatore del capo è nullo, c'è solo un elemento della lista, in modo da invertire non si fa nulla.

se la testa = null poi tornare
se testa-> next = null poi ritorno

2 Inizializzare tre puntatori: prev, correnti e successivi. \ "Indietro \" e \ "corrente \" dovrebbe puntare al nodo principale della lista. \ "Avanti \" dovrebbe puntare al secondo nodo, cercando in puntatore nel nodo testa.

puntatore prev = testa
ANDARE
corrente puntatore = testa
ANDARE
puntatore prossimo = testa-> prossimo;

3 Situato nei pressi del puntatore del nodo testa a null. Il nodo principale diventerà l'ultimo nodo della lista, quindi non ci saranno i nodi dopo di esso.

testa-> next = null

4 Loop attraverso la lista invertendo la direzione dei puntatori. I tre puntatori inizializzati in precedenza vengono utilizzati per tenere traccia della posizione corrente nella lista.

mentre accanto! = null // Un nullo prossimo puntatore significa che abbiamo raggiunto la fine della lista
corrente = prossimo // avanzare il puntatore corrente
prossimo = current-> successiva // Advance il prossimo puntatore
current-> next = prev // Puntare il nodo corrente al nodo precedente, invertendo il link
prev = corrente // Advance l'ultimo puntatore
fine mentre

5 Puntare la variabile testa al nuovo capo della lista.

testa = corrente

Consigli e avvertenze

  • Se è necessario per scorrere una lista collegata in entrambe le direzioni considerazione l'attuazione di una lista doppiamente legata.