Spiegazione visiva Indicazioni necessarie per l'inversione del codice della infrastruttura dell'elenco collegato?

Question

Ho il seguente codice per l'inversione dell'elenco collegato. Mi sto confondendo nel ciclo while e quindi sicuramente apprezzerei se qualcuno potesse fornire una spiegazione visiva di come effettivamente funziona.

static void Reverse (struct node** headRef) 
{ 
    struct node* result = NULL; 
    struct node* current = *headref; 
    struct node* next; 

    while(current != NULL) 
    { 
     next = current->next; 
     current->next = result; 
     result = current; 

     current = next; 
    }  
    *headRef = result; 

} 

Answer 1

OK, ecco il mio tentativo di rendere ancora più chiara la risposta di valya (anche se pensavo che fosse già abbastanza buona):

Supponiamo di avere questa lista:

// a->b->c->d->e->NULL 

Iniziamo al primo nodo, a, che contiene un puntatore (next) per b:

// a->b ... 

La linea next = current->next; insiemi next a b (abbastanza semplice). La riga successiva current->next = result; fa questo:

// NULL<-a b ... (notice there is no longer a pointer from a to b) 

Poi abbiamo result = current; che definisce result-a (di nuovo, abbastanza semplice). Infine, abbiamo l'importante current = next;, che imposta current su b.

Così sulla prossima iterazione del ciclo while, con next set per b, result insieme a a, e current insieme a b, cominciamo sopra:

next = current->next; 

// NULL<-a<-b c ... 
current->next = result; 

result = current; 

Poi lo facciamo di nuovo:

Una volta raggiunto l'ultimo elemento nell'elenco collegato (e in questo esempio), ciò accade:

next = current->next; // next becomes NULL 

// NULL<-a<-b<-c<-d<-e 
current->next = result; 

result = current; // result is now e 

current = next; // current is now NULL 

Ora, dal momento che current è nullo, il ciclo while termina e ci ritroviamo con:

*headRef = result; 

che, come si può vedere ora, rende headRef punto di e, trattando e come il nuovo primo articolo nel nostro elenco collegato, con e->next che punta a d, d->next che punta a c, ecc.

Answer 2

lista sembrava:

=>(1) => => => => => => => => =>(10) 

abbiamo invertito ogni pezzo della lista

<=(1) => => => => => => => => =>(10) 
<=(1) <= => => => => => => => =>(10) 
<=(1) <= <= => => => => => => =>(10) 
... 
<=(1) <= <= <= <= <= <= <= <= <=(10) 

così, ora di inizio è la fine, e siamo in grado di guardare la lista dalla diverso punto e vedere:

=>(10) => => => => => => => => =>(1) 

Answer 3

Ch eck out this sito per una rappresentazione visiva.
Sembra che ci sia una buona spiegazione del codeproject here (vedere la tecnica 3).

Answer 4

ho fatto un diagramma a punti che penso graficamente spiegare cosa sta succedendo:

Link to full-sized image

Ed ecco il (sciatto) fonte di punti nel caso qualcuno si prende cura:

digraph g { 
    label = "Start" 
    subgraph cluster_1 
    { 
     a1 -> b1 -> c1; 
     current1 -> a1; 
     result1 
     a1 [label="a"] 
     b1 [label="b"] 
     c1 [label="c"] 
     current1 [label="current"] 
     result1 [label="result"] 
    } 
    label = "Once through loop" 
    subgraph cluster_2 
    { 
     current2 -> b2; 
     result2 -> a2; 
     b2 -> c2; 
     a2 [label="a"] 
     b2 [label="b"] 
     c2 [label="c"] 
     current2 [label="current"] 
     result2 [label="result"] 
    } 
    label = "Twice through loop" 
    subgraph cluster_3 
    { 
     current3 -> c3; 
     result3 -> b3; 
     b3 -> a3; 
     a3 [label="a"] 
     b3 [label="b"] 
     c3 [label="c"] 
     current3 [label="current"] 
     result3 [label="result"] 
    } 
    label = "Final" 
    subgraph cluster_4 
    { 
     result4 -> c4 -> b4 -> a4; 
     a4 [label="a"] 
     b4 [label="b"] 
     c4 [label="c"] 
     current4 [label="current"] 
     result4 [label="result"] 
    } 
    label = "" 

} 

Answer 5

Vedere here per una buona spiegazione. Eccone l'estratto:

public class List { 
    private class Node { 
     int data; 
     Node next; 
    } 
    private Node head; 

    public void reverse() { 
     if (head == null) return; 
     Node prev = null,curr = head,next = null; 
     while (curr != null) { 
     next = curr.next; 
     curr.next = prev; 
     prev = curr; 
     curr = next; 
     } 
     head = prev; 
    } 
} 

The list: 
========== 
1->2->3->4->5 
------------------------------------------------------------------ 
Running of the code: 
============================ 
At start: 
********** 
head = 1; 
prev = null,curr = 1, next = null 
1st iteration of while loop: 
****************************** 
next = 2; 
2->3->4->5 
curr.next = null; 
1->null 
prev = 1; 
1->null 
curr = 2; 
2->3->4->5 
2nd iteration of while loop: 
****************************** 
next = 3 
3->4->5 
curr.next = 1 
2->1->null 
prev = 2 
2->1->null 
curr = 3 
3->4->5 
3rd iteration of while loop: 
****************************** 
next = 4 
4->5 
curr.next = 2 
3->2->1->null 
prev = 3 
3->2->1->null 
curr = 4 
4->5 
4th iteration of while loop: 
****************************** 
next = 5 
5->null 
curr.next = 3 
4->3->2->1->null 
prev = 4 
4->3->2->1->null 
curr = 5 
5->null 
5th iteration of while loop: 
****************************** 
next = null 
null 
curr.next = 4 
5->4->3->2->1->null 
prev = 5 
5->4->3->2->1->null 
curr = null 
There is no 6th iteration and the while loop terminates since 
curr is null and the check is for curr != null. 
last statement: 
================== 
head = prev 
This statement leaves the list reversed with referencing head with the reversed node prev 
to become the new head node.