Liste récurrente inversée

Je regardais le code ci-dessous de la bibliothèque 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; /* sortingcky step -- see the diagram */ first->next = NULL; /* fix the head pointer */ *head_ref = rest; }

Ce que je ne comprends pas, c’est la dernière étape récursive, par exemple si la liste est 1-2-3-4. Maintenant, pour la dernière étape récursive, la première valeur sera 1 et le rest, égal à 2. Donc, si vous définissez * head_ref = rest .. ça fait la tête de la liste 2 ?? Quelqu’un peut-il s’il vous plaît expliquer comment après avoir inversé la tête de la liste devient 4 ??

Dessinez une trace de 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.

Considérez la liste:

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

Où first pointe sur le premier nœud et rest pointe sur le nœud suivant.

Comme la liste n’est pas vide et que la liste ne contient pas un seul nœud, nous effectuons un appel récursif pour inverser la liste pointée par rest . Voici à quoi ressemble la liste après avoir inversé le rest de la liste:

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

Comme on le voit, le rest pointe maintenant sur la liste inversée qui en a 4 au début et 2 à la fin de la liste. Le pointeur suivant du noeud 2 est NULL .

Nous devons maintenant append le premier noeud à la fin de la liste de repos inversé. Pour append quoi que ce soit à la fin de la liste, nous devons avoir access au dernier nœud de la liste. Dans ce cas, nous devons avoir access au dernier nœud de la liste de repos inversé. Regardez le diagramme, d' first -> next points first -> next à la dernière liste de repos inversé de nœud. Par conséquent, first -> next -> next sera le prochain pointeur du dernier nœud de la liste de repos inversé. Maintenant, nous devons faire en sorte d’ first :

 first -> next -> next = first;

Après cette étape, la liste se présente comme suit:

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

Maintenant, le champ next du dernier nœud de la liste doit être NULL . Mais ce n'est pas le cas maintenant. Le champ next du dernier nœud (nœud 1 ) pointe vers le nœud précédent (nœud 2 ). Pour résoudre ce problème, nous le faisons:

 first -> next = NULL;

Après cela, la liste ressemble à:

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

Comme on le voit, la liste est maintenant correctement inversée, le rest pointant vers le début de la liste inversée.

Nous devons renvoyer le nouveau pointeur principal afin que les modifications soient reflétées dans la fonction appelante. Mais il s’agit d’une fonction void et head est passé en double pointeur. Par conséquent, si vous modifiez la valeur de *head , la fonction appelante verra la modification de la tête:

 *head = rest;

Le rest n’est pas 2 , c’est 2 -> 3 -> 4 , ce qui est inversé de manière récursive. Après cela, nous positionnons *head_ref au rest , qui est maintenant ( *head_ref récursif!) 4 -> 3 -> 2 .

Le point important ici est que, bien que le first et le rest aient le même type, c’est-à-dire node* , ils sont fondamentalement différents sur le plan conceptuel: tout d’ first pointe vers un seul élément, tandis que rest indique une liste d’éléments liés . Cette liste liée est inversée de manière récursive avant d’être affectée à *head_ref .

J’ai récemment écrit une méthode récursive pour inverser une liste chaînée en ruby. C’est ici:

 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