Erreur de segmentation dans une fonction pour inverser une liste liée de manière récurrente

J’implémente une fonction pour inverser de manière récursive une liste chaînée, mais en obtenant segault

typedef struct _node { int data; struct _node *next; } Node, *NodeP; NodeP recursiveReverseList(NodeP first){ if(first == NULL) return NULL; if(first->next == NULL) return first; NodeP rest = recursiveReverseList(first->next); rest->next = first; first->next = NULL; return first; } 

Peux-tu aider s’il te plait?

PS La version itérative fonctionne bien cependant. Ce n’est pas un devoir. Juste pratiquer C.

Merci à tous 🙂

@Unicornaddict a déjà posté un algorithme correct.

Mais, si vous continuez à avoir segmentation fault , je suppose que vous faites une erreur en appelant la fonction depuis main .

Correct:

 head->next = recursiveReverseList(head->next); 

Explication:

  • Passe head->next de la fonction récursive. Si vous passez la head , il fera quelque chose comme

Avant l’appel:
tête —> A —> B —> C
Après appel:
tête <--- A <--- B <--- C

qui fera la head point à NULL et A point à la head

  • Après avoir passé head->next argument head->next en argument, l’état de la liste est:

tête —> A <--- B <--- C

Donc, vous devez vous faire un signe de head ( C dans ce cas).

L’algorithme récursif général pour cela est:

  1. Divide la liste en 2 parties – le premier nœud et le rest de la liste.
  2. Appel récursivement inversé pour le rest de la liste liée.
  3. Lien rest au first .
  4. Pointeur de head fixe

Vous suivez correctement les étapes 1 et 2, mais je suppose que vous vous êtes trompé aux étapes 3 et 4. Je vous suggérerais d’essayer ceci:

 NodeP recursiveReverseList(NodeP first){ if(first == NULL) return NULL; // list does not exist. if(first->next == NULL) return first; // list with only one node. NodeP rest = recursiveReverseList(first->next); // recursive call on rest. //rest->next = first; CHANGE THIS first->next->next = first; // make first next to the last node in the reversed rest. first->next = NULL; // since first is the new last..make its next NULL. //return first; CHANGE THIS return rest; // rest now points to the head of the reversed list. } 

image http://soffr.miximages.com/c/Linked-List-Rverse.gif .

MODIFIER:

PS: Je n’ai pas testé cela. Alors essayez et faites le nous savoir 🙂

J’ai testé la fonction ci-dessus et semble fonctionner comme prévu. Vous pouvez essayer le programme ici: http://ideone.com/bQXAV

Votre algorithme semble être faux. Vous devez renvoyer le pointeur à l’en-tête de la nouvelle liste, mais vous renvoyez le pointeur au dernier élément.

En effet, vous avez peut-être besoin des deux: un pointeur sur la tête et le pointeur sur le dernier élément.

je pense

 rest->next = first; 

devrait être

 first->next->next = first;