Linked lista recursiva inversa

Question

yo estaba buscando en el código de abajo de Stanford biblioteca:

void recursiveReverse(struct node** head_ref) 
{ 
    struct node* first; 
    struct node* rest; 

    /* empty list */ 
    if (*head_ref == NULL) 
     return; 

    /* suppose first = {1, 2, 3}, rest = {2, 3} */ 
    first = *head_ref; 
    rest = first->next; 

    /* List has only one node */ 
    if (rest == NULL) 
     return; 

    /* put the first element on the end of the list */ 
    recursiveReverse(&rest); 
    first->next->next = first; 

    /* tricky step -- see the diagram */ 
    first->next = NULL;   

    /* fix the head pointer */ 
    *head_ref = rest; 
} 

Lo que no entiendo es en el último paso recursivo para, por ejemplo si la lista está 1-2-3-4 Ahora para el último paso recursivo, primero será 1 y el resto será 2. Entonces, si establece * head_ref = rest ... ¿eso hace que el encabezado de la lista 2? ¿Puede alguien explicar por favor cómo después de invertir el encabezado de la lista se convierte en 4?

Answer 1

El resto no es 2, es 2 -> 3 -> 4, que se invierte de forma recursiva. Después de eso establecemos *head_ref en rest, que ahora (recíprocamente se invierte!) 4 -> 3 -> 2.

El punto importante aquí es que aunque ambos first y rest tienen el mismo tipo, es decir node*, que son conceptualmente fundamentalmente diferente: first puntos a un solo elemento, mientras rest apunta a una lista de elementos vinculados. Esta lista vinculada se invierte de forma recursiva antes de asignarse al *head_ref.

Answer 2

Es necesario realizar un seguimiento de la pila ...

Intial - {1,2,3,4} 
Head - 1 
Rest = 2,3,4 
Recurse(2,3,4) 
Head = 2 
Rest = 3,4 
Recurse(3,4) 
Head = 3 
Rest = 4 
Recurse (4) 
Head = 4 
Rest = null //Base Case Reached!! Unwind. 

So now we pick up 
Recurse(3,4) 
Head = 3 
Rest = 4 
// Return picks up here 
first->next->next = first; 
so list is: 
3,4,3 
// set head to null, 
null ,4,3, 
//Off with his head! 
4,3 
Return 

Now we're here 
Recurse(2,3,4) 
Head = 2 
Rest = 3,4 
Previous return leaves state as: 
Head = 2 //But Head -> next is still 3! -- We haven't changed that yet.. 
Rest = 4,3 
Head->next is 3, 
Head->next->next = 2 makes the list (actually a tree now) 
4->3->2 
^
    | 
    2 
And chop off the head leaving 
4->3->2 
and return. 

Similarly, do the last step which will leave 
4->3->2->1 
    ^
     | 
     1 
and chop off the head, which removes the one. 

Answer 3

examinar la lista:

1 -> 2 -> 3 -> 4 -> NULL 
^ ^
    |  | 
first rest 

Dónde first apunta al primer nodo y descansan puntos al siguiente nodo a first.

Como la lista no está vacía y la lista no contiene un nodo, hacemos una llamada recursiva al reverse para invertir la lista apuntada por rest. Así es como se ve la lista después de invertir el resto de la lista:

1 -> 2 <- 3 <- 4 
^ |   ^
    |  NULL   | 
first     rest 

Como se ve rest ahora apunta a la lista invertido que tiene 4 al principio y 2 al final de la lista. El siguiente puntero del nodo 2 es NULL.

Ahora tenemos que agregar el primer nodo al final de la lista de descanso invertido. Para agregar algo al final de la lista, necesitamos tener acceso al último nodo de la lista. En este caso, necesitamos tener acceso al último nodo de la lista de descanso invertido. Mire el diagrama, first -> next apunta a la lista del último nodo invertido-resto. Por lo tanto, first -> next -> next será el siguiente puntero del último nodo de la lista de descanso invertido. Ahora tenemos que hacer que apunte a first por lo que hacemos:

first -> next -> next = first; 

Después de este paso, la lista se parece a:

1 <- 2 <- 3 <- 4 
^->    ^
    |     | 
first     rest 

Ahora el campo del último nodo de la lista next debe haber NULL. Pero no es el caso ahora. El campo next del último nodo (nodo 1) apunta al nodo anterior (nodo 2).Para solucionar este problema que hacemos:

first -> next = NULL; 

Después de esto la lista se parece a:

NULL <- 1 <- 2 <- 3 <- 4 
     ^    ^
     |     | 
     first     rest 

Como se ve la lista ahora se invierte correctamente con rest apuntando a la cabeza de la lista invertida.

Tenemos que devolver el nuevo puntero de la cabeza para que los cambios se reflejen en la función de llamada. Pero esta es una función void y head se pasa como puntero doble por lo que cambiar el valor de *head hará la función de llamar a ver la cabeza cambiada:

*head = rest; 

Answer 4

Hace poco escribí un método recursivo para revertir una lista enlazada en rubí. Aquí está:

def reverse!(node_1 = @head, node_2 = @head.link) 
    unless node_2.link 
     node_2.link = node_1 
     @head = node_2 
     return node_1 
    else 
     return_node = reverse!(node_1.link, node_2.link) 
     return_node.link = node_1 
     node_1.link = nil 
     return node_1 
    end 
    return self 
end