Lista enlazada inversa recursiva

5 minutos de lectura

avatar de usuario
Fénix

Estaba mirando el siguiente código 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 es 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. Entonces, si configura *head_ref = rest .. que hace la cabeza de la lista 2?? ¿Alguien puede explicar cómo después de invertir el encabezado de la lista se convierte en 4?

Dibuje 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. 

  • ¡Gran explicación! ¡Muchas gracias!

    – harihb

    9 de junio de 2011 a las 4:21

  • @chris: *head_ref = descanso; No lo entiendo… por favor ayúdame a superar esto.

    – kTiwari

    13 de septiembre de 2012 a las 12:41

  • head_ref es una referencia al primer nodo en la (sub) lista en el nivel actual de recursividad. El resto se refiere al primer nodo en el resto de la lista. Por lo tanto, establecer head_ref en reposo tiene el efecto de cortar la cabeza anterior.

    – Chris Cudmore

    13 de septiembre de 2012 a las 12:45

  • Gracias por el seguimiento de la pila.

    – Makesh

    1 de septiembre de 2013 a las 11:57

  • @ChrisCudmore Indique cómo rest conserva su valor como 4 (es decir, el último elemento de la lista real) después del retroceso de la recursividad. ¿Es porque estamos pasando la dirección de descanso en la llamada a la función? ¿Coincide con el mismo nombre de la variable?

    – Surbhi Jain

    12 de noviembre de 2017 a las 19:52

Considere la lista:

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

Donde first apunta al primer nodo y el resto apunta al nodo siguiente first.

Dado que la lista no está vacía y la lista no contiene un nodo, hacemos una llamada recursiva a reverse para invertir la lista señalada 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 vio 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 necesitamos agregar el primer nodo al final de la lista de descanso invertido. Para agregar algo al final de la lista, debemos tener acceso al último nodo de la lista. En este caso necesitamos tener acceso al último nodo de la lista de descanso invertido. Mira el diagrama, first -> next apunta a la lista de reposo 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 a first entonces hacemos:

first -> next -> next = first;

Después de este paso, la lista se ve así:

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

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

first -> next = NULL;

Después de esto, la lista queda así:

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

Como se ve, la lista ahora está correctamente invertida con rest apuntando al encabezado de la lista invertida.

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

*head = rest;

  • impresionante explicación. Gracias

    – bolsa

    16 de junio de 2013 a las 20:35

el resto no es 2su 2 -> 3 -> 4que se invierte recursivamente. Después nosotros fijamos *head_ref para restque ahora es (¡recursivamente al revés!) 4 -> 3 -> 2.

El punto importante aquí es que aunque ambos first y rest tienen el mismo tipo, es decir node*son conceptualmente fundamentalmente diferentes: first puntos a uno solo elemento, mientras rest apunta a un lista enlazada de elementos Esta lista enlazada se invierte recursivamente antes de que se asigne a *head_ref.

Recientemente escribí un método recursivo para invertir una lista enlazada en Ruby. Aquí lo tienes:

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

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad