Lista enlazada recursiva inversa

algorithm recursion

Question

Estaba mirando el código de abajo de la biblioteca de stanford:

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 está en el último paso recursivo, por ejemplo, si la lista es 1-2-3-4 Ahora, para el último paso recursivo primero será 1 y el resto será 2. Por lo tanto, si establece * head_ref = rest .. Eso hace que el jefe de la lista 2? ¿Alguien puede explicar cómo después de invertir el encabezado de la lista se convierte en 4?

Answer 1

Considera la lista:

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

Donde el first apunta al primer nodo y el resto apunta al nodo próximo al first .

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

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

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

Ahora debemos 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, debemos tener acceso al último nodo de la lista de descanso invertido. Mire el diagrama, first -> next puntos a la lista de descanso invertido del último nodo. 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 first lo que hacemos:

first -> next -> next = first;

Después de este paso la lista se ve como:

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

Ahora el next campo del último nodo de la lista debe ser NULL . Pero ahora no es el caso. El next campo del último nodo (nodo 1 ) apunta al nodo anterior (nodo 2 ). Para arreglar esto hacemos:

first -> next = NULL;

Después de esto la lista se ve como:

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

Como se ve, la lista ahora se invierte correctamente y el rest apunta al encabezado de la lista invertida.

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

*head = rest;

Answer 2

Dibuja un rastro de 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

El resto no es 2 , es 2 -> 3 -> 4 , que se invierte recursivamente. Después de eso , configuramos *head_ref en rest , que ahora está (¡invertido de forma recursiva!) 4 -> 3 -> 2 .

El punto importante aquí es que, si bien el first y el rest tienen el mismo tipo, es decir, node* , son conceptualmente diferentes: los first puntos apuntan a un solo elemento, mientras que el rest apunta a una lista enlazada de elementos. Esta lista enlazada se invierte recursivamente antes de asignarse a *head_ref .

Answer 4

Recientemente escribí un método recursivo para revertir una lista vinculada en ruby. 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