Vous ne savez pas exactement pourquoi ma fonction de suppression de liste liée récursive fonctionne? J'adorerais une explication

Question

J'ai écrit un programme, et cela fonctionne, mais je ne pense pas qu'il devrait. Quelqu'un peut-il expliquer pourquoi cela fonctionne?

J'ai une liste à lien unique. Ceci est pour un projet, donc je ne peux pas code postal direct, mais changer Ill le problème un peu

Disons que ma liste chaînée est une liste de numéros 1, 2, 3, 4, 4, 5

J'ai besoin pour scanner la liste et supprimer les doublons, je dois donc supprimer l'un des 4. Et j'ai besoin de le faire via la récursivité.

La fonction que je suis en train d'écrire a son argument/paramètre comme le pointeur au début de la liste, j'appellerai ce pointeur

//Base cases up here 
if (pointer->value == pointer->next->value){ 
    *toDelete = pointer; 
    pointer = pointer->next; 
    delete toDelete; 
    recur the function 
} else recur(pointer->next); 

Maintenant, ce code fonctionne, et je ne pense pas qu'il devrait parce que Je ne connecte jamais le noeud précédent à celui après le noeud que je supprime. Pourtant, quand je regarde le résultat, tous les nœuds appropriés sont connectés et tous ceux qui étaient censés être supprimés sont supprimés. Suis-je mal compris quelque chose ici? pointer = pointeur-> suivant faire plus que simplement pointer pointeur à l'adresse du nœud suivant?

Merci!

Answer 1

Maintenant, ce code fonctionne, et je ne pense pas qu'il devrait, car je ne connecte jamais le nœud précédent à celui après le nœud que je supprime.

C'est correct. Votre fonction peut sembler fonctionner, mais elle montre vraiment des signes de comportement indéfini. Vous devez utiliser:

if (pointer->next != nullptr && pointer->value == pointer->next->value){ 
    auto toDelete = pointer->next; 
    pointer->next = pointer->next->next; 
    delete toDelete; 

    // Recurse with the same pointer since you might have 4 4 4 
    // in the original list. 
    recur(pointer); 
} 
else {  
    recur(pointer->next); 
}