On m'a demandé récemment dans un entretien d'embauche de développer un algorithme capable de déterminer si une liste liée est cyclique. Comme c'est une liste liée, nous ne connaissons pas sa taille. C'est une liste doublement liée avec chaque noeud ayant des pointeurs «suivants» et «précédents». Un nœud peut être connecté à tout autre nœud ou peut être connecté à lui-même.
La seule solution que je suis arrivée à cette époque était de choisir un nœud et de le vérifier avec tous les nœuds de la liste liée. L'intervieweur n'a évidemment pas aimé l'idée car ce n'est pas une solution optimale. Quelle serait une meilleure approche?
11 Réponses :
La solution générale consiste à avoir 2 pointeurs qui se déplacent à des taux différents. Ils seront éventuellement égaux si une partie de la liste est circulaire. Quelque chose le long des lignes de ceci: flagramment volé d'ici: http: // ostermiller.org/finind_loop_snel_linked_list.html
Vous pouvez gérer une liste de circulaire complète générale comme ceci: boucle via la liste liée via le premier élément jusqu'à atteindre la fin de la liste ou jusqu'à ce que vous reveniez au premier élément.
Mais si vous voulez gérer le cas où une partie de la liste est circulaire, vous devez également aller de l'avant votre premier pointeur périodiquement.
Vous ne revenez pas au premier élément si la liste contient un cycle qui ne commence pas au premier élément.
@Mike: Oui Voir la deuxième partie, peut-être que vous avez écrit cela comme je l'écrivais encore.
Dans une liste liée unidimensionnelle, la liste complète est un cycle, soit la liste ne contient pas de cycles.
@JOHNMCG: D'accord mais je pense que ce n'est pas l'intention des affiches. Je pense qu'ils veulent détecter des choses telles que A-> B-> C-> D-> C-> D-> C-> D-> C-> D ...
@Brian r
Commencez avec deux pointeurs pointant sur le même élément. Marchez un pointeur dans la liste, suivez les pointeurs suivant . L'autre marche la liste suivant les pointeurs précédent . Si les deux pointeurs se rencontrent, la liste est circulaire. Si vous trouvez un élément avec un Précédent ou suivant Pointeur défini sur null , alors vous savez que la liste est pas circulaire.
Cela ne fonctionne pas. La liste peut avoir un cycle quelque part dans celui-ci qui ne sera pas trouvé par cet algorithme.
Si vous faites cela dans une boucle, ne déplacez pas les deux pointeurs sur chaque itération. Si vous l'avez fait et que le nombre d'éléments de la liste est étrange, les pointeurs se passeraient probablement avant de vérifier s'ils se sont rencontrés.
@Mike Daniels - L'OP essayait de détecter si une liste était cyclique, non pas si un cycle existe dans une liste (ou au moins c'est comment j'ai lu la question). @Scott Langham- Merci, j'aurais dû clarifier ce point de ma réponse. Chaque itération ne fait qu'un pointeur. La raison du déplacement de deux dans des directions opposées est de trouver la fin de la liste (s'il n'est pas circulaire) plus rapidement.
@Scott, aucune utilisation tente d'améliorer cela. Si j'ai une liste liée A-> B-> C-> D-> B, et je commence les deux pointeurs à A, je suis déjà foutu.
Dans une liste liée à une dimension, la liste complète est un cycle ou la liste ne contient pas de cycle. Une sous-liste n'est pas une sous-liste qui est un cycle, ou un nœud de la liste qui est en dehors du cycle. Si c'était des graphiques, ce serait une histoire différente.
@Mike Daniels - La liste A-> B-> C-> D-> B est en dehors du champ d'application de cette question car il s'agit d'une liste doublement liée et d'élément B n'aurait pas clair Précédent Pointeur dans votre exemple.
Ce que vous cherchez est un algorithme de recherche de cycle. L'algorithme Joel fait référence à l'algorithme «Tortue et Hare» ou l'algorithme de recherche du cycle de Floyd. Je préfère la seconde parce que cela ressemble à ce qu'il ferait un bon sort D & D.
Vue d'ensemble de Wikpedia des algorithmes de recherche de cycle , avec code d'échantillon
Stepanov donne une planification très lisible de celui-ci dans ses éléments de la programmation .
[Modifier la question et sujet a été reformulé afin de préciser que nous vérifions des cycles dans une liste doublement chaînée, ne vérifie pas si une liste doublement chaînée est simplement circulaire, de sorte que les parties de ce poste peuvent être hors de propos.]
Son un lien double liste avec chaque noeud ayant « après » et pointeurs « précédents ». p> Blockquote>
listes Doublement liés sont souvent mis en œuvre avec la tête et la queue de la liste pointant vers NULL pour indiquer où ils se terminent. P>
[Modifier] Comme l'a souligné, cela ne vérifie si la liste est circulaire dans son ensemble, et non pas si elle a des cycles dans, mais qui a été le libellé de la question initiale. em> Si la liste est circulaire, de queue> suivante == tête et / ou BANDEAUX> prev == queue. Si vous n'avez pas accès à la fois le nœud de la queue et la tête et seulement un de ceux mais pas les deux, il devrait suffire simplement vérifier si BANDEAUX> prev! = NULL ou de queue> suivante! = NULL. p>
Si ce n'est pas une réponse suffisante parce que nous ne nous donne que un nœud aléatoire [et la recherche de cycles partout dans la liste], tout ce que vous avez à faire est de prendre ce nœud aléatoire et garder parcourir la liste jusqu'à ce que vous atteignez un noeud concordant (auquel cas il est circulaire) ou un pointeur nULL (auquel cas ce n'est pas). p>
Cependant, cela est essentiellement la même chose que la réponse que vous avez déjà fourni que l'intervieweur n'a pas aimé. Je suis tout à fait certain que, sans bidouille magique, il n'y a aucun moyen de détecter un cycle dans une liste chaînée, sous un nœud aléatoire, sans un algorithme de complexité linéaire. P>
[Modifier] Mon esprit a engrenages commutées maintenant avec l'accent mis sur la détection des cycles dans une liste par opposition à déterminer si une liste chaînée est circulaire p>
Si nous avons un cas comme.: 1 2 3 [2] p>
La seule façon que je peux voir que nous pouvons détecter des cycles est de garder une trace de tous les éléments que nous traversions jusqu'à présent et regarder pour un match le long du chemin. p>
Bien sûr, cela pourrait être pas cher. Si nous avons le droit de modifier les nœuds de la liste, nous pourrions garder un drapeau simplement traversé avec chaque nœud que nous fixons comme nous le faisons. Si nous rencontrons un nœud avec ce drapeau déjà défini, nous avons trouvé un cycle. Cependant, ce ne serait pas bien pour le parallélisme. P>
Il y a une solution proposée ici [que j'ai volé une autre réponse] appelé « cycle-algorithme de recherche de Floyd ». Jetons un coup d'oeil (modifié pour le rendre un peu plus facile pour moi de lire). P>
function boolean hasLoop(Node startNode) { Node fastNode2 = startNode; Node fastNode1 = startNode; Node slowNode = startNode; while ( slowNode && (fastNode1 = fastNode2.next()) && (fastNode2 = fastNode1.next()) ) { if (slowNode == fastNode1 || slowNode == fastNode2) return true; slowNode = slowNode.next(); } return false; }
Je suis presque positif que la question de l'entrevue était en réalité sur la détection si la liste a un cycle n'importe où, qui ne commence pas nécessairement au premier élément.
Cela n'atteint que le cas où toute la liste est circulaire. Habituellement, l'intervieweur préférerait une solution complète
@Joel Oui, mais d'abord, j'ai modifié le poste pour faire face aux cas où la liste n'est que partiellement circulaire et y a un cycle. Deuxièmement, nous devons noter que l'OP a déjà fourni ce que je considérerais la bonne réponse pour le cas qui doit continuer à traverser linéairement jusqu'à ce que nous trouvions le même nœud ou la fin de la liste.
@ Joel sauf s'il y a une solution de complexité linéaire plus rapide, ce n'aurait-il pas le fait que l'intervieweur a rejeté cette réponse impliquant qu'il existe des informations contextuelles supplémentaires sur la liste que nous pouvons utiliser?
@ STINKY472 La solution de l'OP consiste à comparer chaque noeud à tous les autres nœuds - qui est quadratique, pas linéaire. S'il ne compare qu'un seul noeud, il manquera des cycles plus loin dans la liste.
@Joel Mon esprit a commuté les engrenages après la reformulation de la question à la liste des cycles que de détecter si une liste est une liste circulaire. Que l'ancien libellé m'a juste jeté complètement. Pourriez-vous examiner la solution proposée que j'ai maintenant et me donner vos pensées? Maintenant je suis curieux aussi.
@ STINKY472 Les deux solutions fonctionnent avec des mises en garde - la première solution nécessite une table de hachage efficace qui nécessiterait O (n) espace. La seconde est moins générale car elle exige de modifier le nœud.
@Joel maintenant je pose des questions dans mes réponses, Doh, mais pourriez-vous regarder ce que j'ai fait avec l'affaire de tortue et de hare (en utilisant trois itérateurs) et de voir ce que j'ai mal fait?
@ stky472 Votre itérateur rapide se déplace à la même vitesse que votre itérateur lent. La trace actuelle ressemble à ceci: [1,2,3], [2,4,5], [3,6,2], [4,3,4] - et vous avez terminé.
@JOEL OOH Nice, bonne prise. J'étais juste en train de regarder l'itérateur rapide qui s'appelle ensuite et je me demandais à ce sujet. Je ne sais pas quoi faire avec la réponse maintenant puisqu'il était basé sur un malentendu de la question. :-RÉ
@Joel Cela aurait été terriblement difficile à proposer sur la place de l'entrevue. Je suppose que l'intervieweur cherchait quelqu'un qui était déjà familiarisé avec ces algorithmes de détection cycliques.
Gardez un hachage de valeurs de pointeur. Chaque fois que vous visitez un nœud, hash son pointeur et le stockez. Si vous venez de visiter un qui a déjà été stocké, vous savez que votre liste est circulaire.
Ceci est un algorithme O (n) si votre table de hachage est constante.
Je pense que c'est O (n) même si votre table de hachage se développe automatiquement.
Une autre option est que, puisque la liste est doublement liée, vous pouvez traverser la liste et vérifier si le prochain pointeur précédent est toujours le nœud actuel ou null et non la tête. L'idée ici est qu'une boucle doit englober la liste entière ou regarder quelque chose comme ceci: au noeud * Il y a 2 liaisons entrantes que l'une seule peut être la précédente. quelque chose comme:
+1 Pour l'idée, mais le code comme écrit revient toujours vrai si les deux premiers nœuds ne sont pas nuls.
@Dave l.: Bonne prise. Je pense que cela le corrige cependant.
supposer que quelqu'un dit "ici un pointeur à un membre d'une liste. Est-ce un membre d'une liste circulaire?" Ensuite, vous pouvez examiner tous les membres accessibles dans une direction de la liste des pointeurs sur un nœud One que vous receviez un pointeur dans leur pointeur qui devrait vous éloigner de votre part. Si vous décidez d'aller dans la direction Suivant , vous recherchez Vous pouvez étendre ceci en allant dans les deux sens en même temps et en voyant si vous vous heurtez à vous-même, mais cela devient plus compliqué et cela ne vous sauve vraiment rien. Même si vous avez implémenté cela avec 2 threads sur une machine multi-noyau, vous traiteriez des comparaisons de mémoire volatile partagées, ce qui tuerait la performance.
alternativement, si vous pouvez marquer chaque nœud de la liste, vous pouvez essayer de déterminer s'il y avait un cycle en recherchant votre marque pendant que vous avez recherché la fin. Si vous avez trouvé votre marque dans un nœud, vous sauriez que vous aviez été là auparavant. Si vous avez trouvé une fin avant de trouver une de vos marques, vous sauriez que ce n'était pas circulaire. Cela ne fonctionnerait pas d'un autre fil essayait de le faire en même temps, cependant, car vous obtiendrez vos marques mélangées, mais l'autre mise en œuvre ne fonctionnerait pas si d'autres threads réorganisaient la liste en même temps que le test . Suivant des pointeurs égaux au pointeur que vous avez été donné. Si vous choisissez d'accéder à la direction prev , vous recherchez prev des pointeurs qui correspondent au pointeur que vous avez été donné. Si vous atteignez un pointeur null dans les deux sens, vous avez trouvé la fin et sachez qu'il n'est pas circulaire.
Ce dont vous avez besoin est Algorithme de recherche de cycle de Floyd . Vous pouvez également penser à trouver le point d'intersection du cycle comme devoirs.
Il est incroyable à quel point les solutions complexes peuvent se propager.
Voici un minimum absolu requis pour déterminer si une liste liée est circulaire: p>
bool is_circular(node* head)
{
node* p = head;
while (p != nullptr) {
p = p->next;
if (p == head)
return true;
}
return false;
}
Ceci est une boucle infinie si le cycle commence quelque part autre que la tête de la liste.
Voici une approche propre pour tester si une liste liée a des cycles de cycles (s'il est cyclique) basé sur l'algorithme de Floyd:
int HasCycle(Node* head)
{
Node *p1 = head;
Node *p2 = head;
while (p1 && p2) {
p1 = p1->next;
p2 = p2->next->next;
if (p1 == p2)
return 1;
}
return 0;
}
Est-ce la même chose que Stackoverflow.com/Questtions/1442008/...
Votre solution originale n'était pas une solution car si vous prenez un nœud à l'extérieur du cercle, votre solution fera une boucle infinie. C'est loin de "optimal". Habituellement, dans une interview, une mauvaise solution est également acceptable, s'il s'agit d'une solution.
Voulez-vous vérifier si toute la liste est cyclique ou si un cycle existe dans la liste?
Je déteste des questions d'entretien comme celui-ci. Si quelqu'un connaît la réponse, tout ce qu'il vous dit, c'est qu'ils connaissent la réponse. S'ils ne connaissent pas la réponse "droite", comment sont-ils censés comprendre? Chance aveugle? Bah. J'ai entendu parler de cette question comme "Comment trouver le nœud moyen d'une liste liée?", Qui a la même solution et les mêmes problèmes qu'une question d'entrevue. Je pense que ceux-ci ont été appelés "aha!" questions sur les épisodes passés du SO Podcast.
Je dirais que c'était un double de SO 3001695 , sauf qu'il a été fermé comme un duplicata de trois autres: SO 2338683 et SO 494830 et SO 34249 . Puisque 34249 est le plus tôt, il "gagne" ...
en double possible de meilleur algorithme de tester si un lien la liste a un cycle
@Codisme: Je pense que l'hypothèse serait qu'il choisissait un nœud de la liste et a traversé la liste jusqu'à ce qu'il l'ait trouvé ou une extrémité (Null PTR). Alors il le saurait.
Je pense que ceci est une question invalide. Êtes-vous juste remis un pointeur à un membre aléatoire de la liste sans plus d'informations? Dans une réelle implémentation, vous auriez probablement une structure qui contenait la liste de la liste et la conception de cela dicterait s'il était circulaire ou non. Et théoriquement, vous ne pourrez peut-être jamais découvrir qu'une liste circulaire est circulaire si elle est infiniment grande.
@Carl Norum, la première fois que j'ai entendu cette question, j'ai pu résoudre sans avoir entendu la réponse. Ce n'est donc pas impossible. La deuxième fois non seulement je ne pouvais-je pas comprendre, je ne me souvenais pas que j'avais entendu la question auparavant. Je ne sais pas si cela renforce votre point ou non.