Comment déterminer si une liste liée a un cycle en utilisant seulement deux emplacements de mémoire
Est-ce que quelqu'un connaît un algorithme pour trouver si une liste liée boucle sur elle-même en utilisant seulement deux variables pour traverser la liste. Disons que vous avez une liste d'objets liés, peu importe le type d'objet. J'ai un pointeur vers la tête de la liste liée dans une variable et je suis une autre variable pour parcourir la liste avec.
Donc, mon plan est de comparer les valeurs de pointeur pour voir si les pointeurs sont les mêmes. La liste est de taille finie, mais peut être énorme. Je peux définir les deux variable à la tête, puis traverser la liste avec l'autre variable, en vérifiant toujours si elle est égale à l'autre variable, mais, si je frappe une boucle, je n'en sortirai jamais. Je pense que cela a à voir avec différents taux de traversée de la liste et de comparaison des valeurs de pointeur. Toutes les pensées?
7 réponses
Je conseille Floyd's Cycle-Finding Algorithm aka Le Tortoise and the Hare Algorithm. Il a une complexité O(n) et je pense que cela correspond à vos besoins.
Exemple de code:
function boolean hasLoop(Node startNode){
Node slowNode = Node fastNode1 = Node fastNode2 = startNode;
while (slowNode && fastNode1 = fastNode2.next() && fastNode2 = fastNode1.next()){
if (slowNode == fastNode1 || slowNode == fastNode2) return true;
slowNode = slowNode.next();
}
return false;
}
Plus D'infos sur Wikipedia: algorithme de recherche de cycle de Floyd .
Vous pouvez utiliser l'algorithmetortue et lapin .
Wikipedia a une explication aussi, et ils l'appellent "algorithme de recherche de cycle de Floyd " ou "tortue et lièvre"
Absolument. Une solution peut en effet traverser la liste avec les deux pointeurs, l'un voyageant à deux fois le taux de l'autre.
Commencez par le pointeur' lent 'et le pointeur' rapide ' pointant vers n'importe quel emplacement de la liste. Exécutez la boucle de traversée. Si le pointeur "rapide" à tout moment coïncide avec le pointeur lent, vous avez une liste circulaire liée.
int *head = list.GetHead();
if (head != null) {
int *fastPtr = head;
int *slowPtr = head;
bool isCircular = true;
do
{
if (fastPtr->Next == null || fastPtr->Next->Next == null) //List end found
{
isCircular = false;
break;
}
fastPtr = fastPtr->Next->Next;
slowPtr = slowPtr->Next;
} while (fastPtr != slowPtr);
//Do whatever you want with the 'isCircular' flag here
}
J'ai essayé de résoudre cela moi-même et j'ai trouvé une solution différente (moins efficace mais toujours optimale).
L'idée est basée sur l'inversion d'une liste chaînée en temps linéaire. Cela peut être fait en faisant deux swaps à chaque étape de l'itération sur la liste. Si q est l'élément précédent (initialement nulle) et p est le courant, le swap(q,p->suivant) swap(p,q) inverse le lien et de faire progresser les deux pointeurs en même temps. Les swaps peuvent être effectués en utilisant XOR pour éviter d'avoir à utiliser une troisième mémoire emplacement.
Si la liste a un cycle, à un moment donné de l'itération, vous arriverez à un nœud dont le pointeur a déjà été modifié. Vous ne pouvez pas savoir quel nœud est, mais en continuant l'itération, en échangeant deux fois certains éléments, vous arrivez à nouveau en tête de la liste.
En inversant la liste deux fois, la liste reste inchangée dans le résultat et vous pouvez dire si elle avait un cycle basé sur si vous êtes arrivé à la tête d'origine de la liste ou non.
int isListCircular(ListNode* head){
if(head==NULL)
return 0;
ListNode *fast=head, *slow=head;
while(fast && fast->next){
if(fast->next->next==slow)
return 1;
fast=fast->next->next;
slow=slow->next;
}
return 0;
}
Passer à l'étape suivante consiste à identifier le cycle (c'est-à-dire non seulement que le cycle existe, mais où il se trouve exactement dans la liste). Tortue et algorithme de lièvre peut être utilisé pour le même, cependant, nous aurons besoin de garder une trace de la tête de la liste à tout moment. Une illustration de cet algorithme peut être trouvée ici .
boolean findCircular(Node *head)
{
Node *slower, * faster;
slower = head;
faster = head->next;
while(true) {
if( !faster || !faster->next)
return false;
else if (faster == slower || faster->next == slower)
return true;
else{
faster = faster->next->next;
}
}
}