Linked lista ricorsiva invertire

Question

stavo guardando il codice qui sotto da Stanford libreria:

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; 
} 

Quello che non capisco è l'ultimo passo ricorsivo per esempio se la lista è 1-2-3-4 Ora per l'ultimo passo ricorsivo prima sarà 1 e resto sarà 2. Quindi, se si imposta * head_ref = rest .. che rende il capo della lista 2 ?? Qualcuno può spiegare come dopo aver invertito la testa della lista diventa 4 ??

Answer 1

Il resto non è 2, è 2 -> 3 -> 4, che viene invertito in modo ricorsivo. Dopo questo impostiamo *head_ref in rest, che ora è (invertito in modo ricorsivo!) 4 -> 3 -> 2.

Il punto importante è che, sebbene sia first e rest hanno lo stesso tipo, cioè node*, sono concettualmente fondamentalmente differenti: first punti un'unica elemento, mentre rest punti ad un elenco degli elementi collegati. Questo elenco collegato viene invertito in modo ricorsivo prima di essere assegnato a *head_ref.

Answer 2

Estrarre una traccia dello stack ...

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

consideri l'elenco:

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

Dove first punti al primo nodo e di riposo punti al nodo successivo alla first.

Poiché l'elenco non è vuoto e l'elenco non contiene un nodo, effettuiamo una chiamata ricorsiva a reverse per invertire l'elenco indicato da rest. Questo è come la lista appare dopo l'inversione del resto della lista:

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

Come visto rest ora punta alla lista che ha invertito 4 all'inizio e 2 alla fine della lista. Il prossimo puntatore del nodo 2 è NULL.

Ora è necessario aggiungere il primo nodo alla fine dell'elenco di inversione inversa. Per aggiungere qualsiasi cosa alla fine dell'elenco, è necessario avere accesso all'ultimo nodo della lista. In questo caso è necessario avere accesso all'ultimo nodo della lista di riposo invertita. Guardare il diagramma, first -> next punti per l'ultimo elenco di riposo invertito del nodo. Pertanto first -> next -> next sarà il prossimo puntatore dell'ultimo nodo della lista di riposo inverso. Ora abbiamo bisogno di farlo puntare a first così facciamo:

first -> next -> next = first; 

Dopo questo passo la lista si presenta come:

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

Ora il campo del l'ultimo nodo della lista next deve essere NULL. Ma non è il caso ora. Il campo next dell'ultimo nodo (nodo 1) punta al nodo precedente (nodo 2).Per risolvere questo problema facciamo:

first -> next = NULL; 

Dopo questa lista si presenta come:

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

Come si è visto l'elenco è ora invertita correttamente con rest che punta alla testa della lista invertita.

Abbiamo bisogno di restituire il nuovo puntatore testa in modo che i cambiamenti si riflettano nella funzione di chiamata. Ma questa è una funzione void e head viene passato come doppio puntatore in modo da cambiare il valore di *head farà la funzione di chiamata vedere la testa mutata:

*head = rest; 

Answer 4

Recentemente ho scritto un metodo ricorsivo per invertire una lista concatenata in Ruby. Eccolo:

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