inversion de la liste chaînée

J’essaie d’inverser une liste chaînée en utilisant la récursivité et j’ai écrit le code suivant. La liste est le début de la liste au début.

node *reverse_list_recursive(node *list) { node *parent = list; node *current = list->next; if(current == NULL) return parent; else { current = reverse_list_recursive(current); current->next = parent; printf("\n %d %d \n",current->value,parent->value); return parent; } } 

Je pouvais voir que tous les liens sont en train de s’inverser. Cependant, lorsque j’essaie d’afficher, je reçois une infinité d’empreintes de chiffres. Je soupçonne une erreur lorsque j’essaie d’inverser le lien pour le premier numéro de la liste.

Qu’est-ce que je fais mal?

Supposons que j’ai une liste chaînée:

  ---------- ---------- ---------- ---------- | 1 | |--->| 2 | |--->| 3 | |--->| 4 | |--->NULL ---------- ---------- ---------- ---------- 

Votre code le convertit en:

  ---------------------- ---------------------- | | | | v | v | ---------- ---------- ---------- ---------- | 1 | |--->| 2 | | | 3 | | | 4 | | ---------- ---------- ---------- ---------- ^ | | | ---------------------- 

Notez que le premier élément pointe toujours vers 2.

Si vous ajoutez la ligne parent->next = NULL après les deux premières, vous obtiendrez:

  ---------------------- ---------------------- | | | | v | v | ---------- ---------- ---------- ---------- NULL<---| 1 | | | 2 | | | 3 | | | 4 | | ---------- ---------- ---------- ---------- ^ | | | ---------------------- 

qui est en fait la structure correcte.

Le code complet est: (Il vous suffit d’imprimer la valeur actuelle pour chaque appel récursif)

 node *reverse_list_recursive(node *list) { node *parent = list; node *current = list->next; if(current == NULL) return parent; else { current = reverse_list_recursive(current); parent->next = NULL; current->next = parent; printf("\n %d \n",current->value); return parent; } } 

Lorsque vous atteignez la fin de la liste, vous retournez le dernier nœud. La valeur suivante de ce dernier noeud est ensuite assignée à lui-même, ce qui crée une incohérence. Si current vaut NULL, retourne NULL à la place et ignore simplement le rest du code si le retour est NULL.

Vous avez oublié de mettre à jour le next membre du premier élément de la liste liée. Add parent->next = NULL; avant l’appel récursif.

Vous devez définir le prochain pointeur de la nouvelle queue (c’est-à-dire l’ancienne tête) sur NULL

EDIT: Voici une version récursive

 node *reverse_list_recursive(node *list) { node *parent = list; node *child = list->next; node *new_head; if (child == NULL) return parent ; /* new head */ new_head = reverse_list_recursive(child) child->next = parent; /* Old parent is the new child of the old child when reversed */ parent->next = NULL; /* might be tail, will be overwritten after we return if we're not at the top level */ return new_head; } 

Je ne vois pas l’avantage de la récursion ici, l’itération fonctionnera tout aussi bien. C’est pour toujours depuis que j’ai écrit C (et il n’ya pas de moyen facile de tester les erreurs de syntaxe suivantes … ou des décharges grincheuses, mais vous avez l’idée).

 node *reversed_list(node *list) { node *fwd=list;//Purely for readability node *last=null; node *next=null; node *rev=null; do { //Cache next next=fwd->next; //Set current rev=fwd; //Reset next to point back rev->next=last; //Update last last=fwd; //Forward ptr; fwd=next; } while (fwd!=null); return rev; } 

Bien sûr, votre *list est inutile après que vous ayez appelé cela car il pointe maintenant sur le dernier élément de la liste qui a ->next=null , pourrait simplement mettre à jour cela au lieu de renvoyer le pointeur.

Mise à jour (pour solution récursive)

Comme d’autres l’ont déjà dit, votre nouvelle queue est foirée (pointe vers le dernier élément, mais doit pointer sur null) … et si vous ne retournez pas la tête correcte, vous renvoyez le deuxième élément. Considérez la liste a->b->null avec votre algorithme:

 p=a, c=b; c= p=b c=null return b; //b->null c=b c->next=a //b->a return a; //a->b, b->a, a returned //But what you wanted is a->null, b->a, and b returned 

Le code mis à jour suivant corrigera:

 node *reverse_list_recursive(node *list) { node *parent = list; node *current = list->next; if(current == NULL) return parent; else { current = reverse_list_recursive(current); current->next = parent; parent->next=null; //Fix tail printf("\n %d %d \n",current->value,parent->value); return current; //Fix head } } 

Avec liste a->b->null :

 p=a, c=b; c= p=b c=null return b; //b->null c=b c->next=a //b->a p->next=null //a->null return b; // b->a->null 

Après la ligne current = reverse_list_recursive(current); vous stockez la nouvelle tête de liste dans current, donc current->next = parent; est faux. Nouveau current est la nouvelle tête de liste, mais vous devez accéder à la nouvelle liste, c’est-à-dire le VIEUX current :

 node* newhead = reverse_list_recursive(current); current->next = parent; printf("\n %d %d \n",current->value,parent->value); return newhead; 

Quelques problèmes que j’ai pu voir:

  • Vous devez faire le prochain pointeur du nouveau dernier nœud NULL.
  • Votre fonction existante va exploser si je lui passe NULL initialement.

Voici le code récursif pour inverser une liste liée.

 list * reverse(list * head) { if( head == NULL || head -> link == NULL ) return head; list *node = reverse( head- > link ); head -> link -> link = head; head -> link = NULL; return node; } 

Plusieurs versions ci-dessus ne fonctionnent pas comme souhaité, voici donc ma version récursive bien testée:

 node * reverseRecursive(node *p,node **head) { if(p->next == NULL) { *head = p; return p; } node *before; before = reverseRecursive(p->next,head); before->next = p; p->next = NULL; return p; } //call from main node*head; //adding value //assuming now head is now 1->2->3->4->NULL node* newHead; reverseRecursive(head,&newHead); //now now newHead is now 4->3->2->1->NULL