Qu'est-ce qu'un algorithme efficace pour déterminer si une liste à un seul lien est circulaire/cyclique ou non? [dupliquer]

un algorithme simple appelé l'algorithme de Floyd doit avoir deux pointeurs, a et b, qui commencent tous deux au premier élément de la liste liée. Puis à chaque pas vous incrémentez a une fois et b deux fois. Répétez jusqu'à ce que vous atteignez la fin de la liste (pas de boucle), ou a == b (la liste contient une boucle).

un autre algorithme est algorithme de Brent .

Trois stratégies principales que je connais:

1. " commencer à parcourir la liste et garder une trace de tous les noeuds que vous avez visités (stocker leurs adresses dans une carte par exemple). Chaque nouveau nœud que vous visitez, vérifiez si vous avez déjà visité. Si vous avez déjà visité le noeud, il y a évidemment une boucle. S'il n'y a pas de boucle, vous finirez par atteindre la fin. Ce n'est pas génial parce que c'est O(N) complexité de l'espace pour stocker le supplément information.

2. La Tortue/le Lièvre de la solution. Démarrez deux pointeurs au début de la liste. Le premier pointeur, La "Tortue" avance un noeud par itération. L'autre pointeur, Le" Lièvre " avance deux noeuds chaque itération. S'il n'y a pas de boucle, le lièvre et la tortue atteindront tous les deux la fin de la liste. S'il y a une boucle, le Lièvre passera devant la tortue à un moment donné et quand cela arrivera, vous savez qu'il y a une boucle. Ce est O(1) espace complexité et un algorithme assez simple.

3. utilisez l'algorithme pour inverser une liste liée. Si la liste a une boucle, vous finirez par revenir au début de la liste tout en essayant de l'Inverser. S'il n'y a pas de boucle, vous finirez de l'inverser et vous atteindrez la fin. Ce est O(1) l'espace de la complexité, mais un peu plus laide de l'algorithme.

je vous comptez vos Nœuds et d'obtenir à la *tête à nouveau.

Que Diriez-vous de l'approche suivante:

triez la liste des liens dans l'ordre croissant en suivant les algorithmes standards. Avant tri: 4-2-6-1-5 Après Tri: 1-2-4-5-6

une fois trié, vérifiez les données de chaque noeud et comparez avec les données du noeud de lien, quelque chose comme ceci:

si(currentcode->données > currentnode->lien->données) c'est à dire la circulaire = true;

à toute comparaison, si l'une des "données courantes->" est plus grande que "currentcode - >link - >data" pour une liste de liens triés, cela signifie que le noeud courant est pointé vers un autre noeud précédent(I. e circulaire);

les gars, je n'ai pas de configuration pour tester le code.Permettez-moi maintenant si ce concept fonctionne.

utilisez algorithme de tortue-lièvre .

@samoz a de mon point de vue la réponse! Pseudo code manquant. Serait quelque chose comme

yourlist est votre liste de liens

allnodes = hashmap
while yourlist.hasNext()
   node = yourlist.next()
   if(allnodes.contains(node))
      syso "loop found"
      break;
   hashmap.add(node)

désolé, le code est très pseudo (faire plus de script java dernièrement)

commencez par un noeud et enregistrez-le, puis itérez la liste entière jusqu'à ce que vous atteigniez un pointeur nul ou le noeud avec lequel vous avez commencé.

quelque chose comme:

Node start = list->head;
Node temp = start->next;
bool circular = false;
while(temp != null && temp != start)
{
   if(temp == start)
   {
     circular = true;
     break;
   }
   temp = temp->next;
}
return circular

C'est O(n), ce qui est à peu près le meilleur que vous pourrez obtenir avec une liste mono-liée (corrigez-moi si je me trompe).

ou pour trouver des cycles dans la liste (comme le milieu), vous pouvez faire:

Node[] array; // Use a vector or ArrayList to support dynamic insertions
Node temp = list->head;
bool circular = false;
while(temp != null)
{
   if(array.contains(temp) == true)
   {
     circular = true;
     break;
   }
   array.insert(temp);
   temp = temp->next;
}
return circular

This sera un peu plus lent en raison de l'insertion fois de tableaux dynamiques.

voici un beau site sur lequel les différentes solutions peuvent être copiées.

trouver la boucle seule liste liée

C'est le gagnant sur ce site

// Best solution
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;
}

Cette solution est celle de Floyd Algorithme de recherche des cycles" publié dans la "Non-déterministe des Algorithmes" par Robert W. Floyd en 1967. Il est également appelé "La Tortue et le Lièvre Algorithme."

un algorithme est:

1. stocker le pointeur vers le premier noeud
2. parcourir la liste en comparant chaque pointeur de noeud à ce pointeur
3. si vous rencontrez un pointeur nul, alors sa liste non circulairement liée
4. si vous rencontrez le premier noeud en traversant alors son une liste circulairement liée

il ne se terminera jamais de la boucle, il peut également être fait dans la solution suivante:

bool hasCircle(List l)
{
   Iterator i = l.begin(), j = l.begin();
   while (true) {
      // increment the iterators, if either is at the end, you're done, no circle
      if (i.hasNext())  i = i.next(); else return false;

      // second iterator is travelling twice as fast as first
      if (j.hasNext())  j = j.next(); else return false;
      if (j.hasNext())  j = j.next(); else return false;

      // this should be whatever test shows that the two
      // iterators are pointing at the same place
      if (i.getObject() == j.getObject()) { 
          return true;
      } 
      if(i.next()==j)
          break;
    }
}

Essayez cette

/* Link list Node */

noeud structurel { de données int; struct Noeud* suivant; };

/ * cette fonction retourne true si donnée liée la liste est circulaire, sinon false. */ bool isCircular(struct Noeud *tête) { // Une liste de liens vide est circulaire si (head = = NULL) return true;

// Next of head
struct Node *node = head->next;

// This loop would stope in both cases (1) If
// Circular (2) Not circular
while (node != NULL && node != head)
   node = node->next;

// If loop stopped because of circular
// condition
return (node == head);

}