Algorithme de détection des boucles de listes chaînées

Question

J'ai lu une question d'entretien en ligne sur la façon de déterminer s'il y a une boucle dans une liste chaînée, et la solution ( L'algorithme de recherche de cycle de Floyd ) est d'avoir deux pointeurs, l'un est 2x plus rapide que l'autre, et de vérifier s'ils se rencontrent à nouveau.

Ma question est la suivante : pourquoi ne puis-je pas garder un pointeur fixe, en déplaçant l'autre pointeur d'un pas à chaque fois ?

Answer 1

Parce que peut-être que la linkedList complète n'est pas dans la boucle.

Pour une liste chaînée lasso algorithme de détection, vous avez besoin de deux pointeurs :

Tant que le premier pointeur est là où se trouve le cow-boy, aucune boucle n'est détectée. Mais si vous le faites avancer pas à pas, il finira par entrer dans la boucle.

---

BTW, lasso est le terminus technicus de la théorie des graphes, cowboy ne l'est pas.

Answer 2

Parce que le premier pointeur (non mobile) peut ne pas se trouver à l'intérieur de la boucle, et donc les pointeurs ne se rencontreront jamais. (Rappelez-vous qu'une boucle peut être constituée d'une partie seulement de la liste).

Answer 3

Parce que la boucle peut ne pas contenir l'élément pointé par le premier pointeur.

Par exemple, si le premier pointeur pointe sur l'élément 1 et que la liste chaînée comporte une boucle par la suite (1->2->3->4->2), votre algorithme ne le détectera pas.