Détection de Cycle (Floyd)
Algorithmique classique
Enonce
Détecter si une liste chaînée contient un cycle en utilisant l'algorithme du lièvre et de la tortue (Floyd). Retourner True s'il y a un cycle.
Signature attendue
def a_cycle(lst: dict) -> bool:Exemple
a_cycle({"val":1,"suiv":{"val":2,"suiv":{"val":3,"suiv":None}}})→False
📖 Rappel de cours
Deux curseurs avancent, l'un d'un pas, l'autre de deux. S'il existe un cycle, le rapide rattrape forcément le lent ; sinon il atteint la fin.
⚠ Le piège : Le rapide fait deux pas : il faut vérifier à chaque tour qu'il peut les faire, sinon on déréférence None. La comparaison porte sur les maillons, pas sur leurs valeurs.
← Exercices Python pour la prépa — CPGE scientifique et ECG
Exercices du meme theme
- Point Fixe dans une Liste Triée
- Liste Chaînée — Création et Affichage
- Inversion d'une Liste Chaînée
- Fusion de Deux Listes Chaînées Triées
- Longueur d'une Liste Chaînée
- Arbre Binaire — Hauteur
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.