Explicación visual ¿Se necesita una guía para revertir el código de la estructura de la lista vinculada?

Question

Tengo el siguiente fragmento de código para revertir la lista enlazada. Me estoy confundiendo en el ciclo while y ciertamente apreciaría si alguien puede proporcionar una explicación visual de cómo realmente está funcionando.

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, aquí está mi intento de hacer que la respuesta de valya sea aún más clara (aunque pensé que ya era bastante buena):

Digamos que tenemos esta lista:

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

Empezamos en el primer nodo, a, que contiene un puntero (next) a b:

// a->b ... 

La línea de next = current->next; conjuntos next a b (Suficientemente simple). La siguiente línea current->next = result; hace esto:

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

entonces tenemos que establece result = current;result-a (de nuevo, bastante simple). Y, por último, tenemos el importantísimo current = next;, que establece current en b.

Así que en la siguiente iteración del bucle while, con next conjunto de b, result conjunto de a y current conjunto de b, empezamos de nuevo:

next = current->next; 

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

result = current; 

Entonces lo hacemos de nuevo:

next = current->next; 

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

result = current; 

Una vez que hemos llegado al último elemento en la lista vinculada (e en este ejemplo), esto sucede:

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 

Ahora, ya current es NULL, el bucle while termina, y nos quedamos con:

*headRef = result; 

que, como se puede ver ahora, hace headRef punto a e, el tratamiento de e como el primer elemento nuevo en nuestra lista vinculada, con e->next apuntando a d, d->next apuntando a c, etc.

Answer 2

lista parecía:

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

invertimos cada pieza de la lista

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

es así, ahora empezar es al final, y podemos mirar la lista de la punto diferente y ver:

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

Answer 3

Ch Eck out this sitio para una representación visual.
Parece una buena explicación de código de proyecto here (ver técnica 3).

Answer 4

hice un diagrama en el punto que creo que gráficamente explicar lo que está pasando:

Link to full-sized image

y aquí está la (descuidado) fuente de puntos en caso de que a alguien le interesa:

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

Ver here para una buena explicación. Aquí está el extracto:

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.