nombre de comptage de noeuds dans une liste, qui peut être circulaire

Voici le problème, il est d'excellents algorithmes de Sedgwick en Java (q 3,54)nombre de comptage de noeuds dans une liste, qui peut être circulaire

reçoit un lien vers un noeud dans une liste chaînée qui ne contient pas Les liens NULL (c'est-à-dire que chaque nœud est lié à lui-même ou à un autre nœud de la liste) déterminent le nombre de nœuds différents sans modifier l'un des nœuds et en n'utilisant pas plus qu'un espace mémoire constant.

Comment faites-vous? parcourir la liste une fois en utilisant l'algorithme lièvre et tortue pour déterminer si elle est circulaire d'une manière ou d'une autre, puis parcourir à nouveau pour voir où la liste devient circulaire, puis parcourir à nouveau en comptant le nombre de nœuds à cette position? ça sonne un peu brutalement, je suppose qu'il y a une solution beaucoup plus élégante.

Source

2009-09-18 Tom

Le tortoise and hare algorithm peut vous donner à la fois la durée du cycle et le nombre de nœuds avant que le cycle commence (λ et u respectivement).

Source

2009-09-18 00:52:53 Artelius

Haha, j'étais en train d'élaborer une réponse élaborée basée sur mon idée que le nombre de pas qu'il faudrait pour qu'une tortue et un lièvre se rencontrent donne des informations sur la durée du cycle, alors que j'aurais dû le rechercher. – Joren

Moi aussi. :(Google est mon ami, Google est mon ami, Google est mon ami ... – TonyOssa

+1 Mais quelle est la complexité temporelle de votre algorithme? Trouver le cycle O (lambda + u), trouver la longueur de cycle O (lambda), trouver la longueur du cou O (lambda * u) Dans l'ensemble c'est toujours O (N^2) en supposant N = min (lambda, u) Y a-t-il un meilleur moyen que quadratique? – Akusete

-4

juste où avez-vous été et si vous êtes arrivés au même noeud c'est fini.

Essayez stocker les entrées dans l'arbre binaire et vous avez O (N * log (n)) et O (N) Espace comlexity

EDIT

Vous pouvez utiliser comlexity espace Log (N) si vous ne stockez pas tous sauf dans le lien d'ordre exponetial. Cela signifie que vous stockez les 1er, 2ème, 4ème, 8ème et 16ème, et si vous êtes touché, vous devez continuer à partir de ce point. Le temps comlexity pour celui-ci est N * log (n)^2

Source

2009-09-18 00:23:39

mais vous ne pouvez utiliser qu'un espace constant – Tom

log (N) est un espace presque constant 100 entrées devraient suffire pour chaque disque/ram dans le monde: D –

@ralu: Désolé, mais 'O (log N)' n'est pas proche à 'O (1)' espace. Pas de loin. – jason

Vérifiez ce: Puzzle: Loop in a Linked List

pointeur de marquage: Dans la pratique, liées listes sont mises en œuvre en utilisant C struct avec au moins un pointeur; une telle structure en C doit être alignée sur 4 octets. Donc les deux bits les moins significatifs sont des zéros. Lors de la traversée de la liste, vous pouvez 'marquer' un pointeur tel que traversé par retournant le bit le moins significatif. Une seconde traversée permet d'effacer ces bits .

Source

2009-09-18 00:29:15

La question indique que vous devriez "déterminer le nombre de nœuds différents sans modifier l'un des nœuds." Même si ce n'était pas une exigence, cette solution sent parce qu'elle repose trop sur un détail d'implémentation et n'est pas agnostique. – jason

@Jason: Qui s'en soucie? Je préférerais un algorithme * rapide * (qui convient à mon environnement) à un algorithme qui fonctionne dans plusieurs langues. Je ne dis pas que cette réponse décrit un algorithme rapide, mais qu'en général, la performance d'un algorithme est plus importante que la portabilité. – Artelius

@Jason, oui il modifie temporairement les nœuds. De toute façon, je sais que ce n'est pas la meilleure solution mais je pense que c'est une solution intéressante. –

La solution la plus élégante est l'algorithme de recherche de cycle de Floyd: http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare

Il fonctionne en O (n), et seulement quantité constante de mémoire est nécessaire.

Source

2009-09-18 00:55:24

nombre de comptage de noeuds dans une liste, qui peut être circulaire

Répondre

Questions connexes