Question: J'ai une liste liée unique (c'est-à-dire une liste avec seulement un pointeur sur le nœud suivant). En outre, il s'agit d'une liste liée circulaire (dans cet exemple, le dernier nœud a un pointeur au premier nœud). Chaque nœud de la liste contient un char.
Un exemple d'une telle liste peut être: A-> B-> C-> B-> A
Maintenant, comment puis-je vérifier si cette liste est un pallindrome?
J'ai pensé à la solution suivante:
Démarrez de la tête de la liste. Trouvez la longueur de la liste, puis le nœud moyen. Commencez maintenant à partir de la tête de la liste et continuez à pousser des éléments en pile jusqu'au milieu. Maintenant, parcourez la liste de l'élément Mid and Pop. Si la valeur de l'élément éclabène est égale à la valeur du nœud actuel. Sinon, renvoyez faux. Sinon, continuez jusqu'à ce que la pile soit vide et que nous avons vérifié tous les caractères. Inconvénients: utilise un espace de pile supplémentaire: (
Démarrez de la tête de la liste. Trouvez la longueur de la liste, puis le nœud moyen. maintenant inverser la 2ème moitié de cette liste. Ensuite, utilisez 2 pointeurs (on pointant pour démarrer et l'autre pointant vers l'élément Mid + 1'th), vérifiez si les valeurs sont identiques. Sinon, renvoyez faux. sinon continue jusqu'à ce que nous atteignions à nouveau le nœud de départ. Inconvénients: Modification de la structure de données d'origine.
Y a-t-il un moyen plus élégant d'aborder ce problème (ce qui, espérons-le, n'utilise pas O (n) espace supplémentaire ou change la liste d'origine)? Je suis intéressé par l'algorithme plutôt que toute mise en œuvre spécifique.
merci
5 Réponses :
Ceci est dans Pseudo-Haskell (je ne me souviens pas de la syntaxe exacte de ces jours) et j'ai écrit pour le cas non circulaire - pour résoudre ce problème, il suffit de remplacer la clause correspondant à [] avec quelque condition Utiliser pour identifier votre cercle complet.
p(xs) = q(xs, Just(xs)) != Nothing
q([], maybeYs) = maybeYs
q(x : xs, Nothing) = Nothing
q(x : xs, maybeYs) =
let maybeZs = q(xs, maybeYs) in
case maybeZs of
Nothing -> Nothing
Just (x :: zs) -> Just(zs)
otherwise -> Nothing
Pouvez-vous l'expliquer, ignorant HASKELLL :(
@Alanfoster - Salut. "Haut niveau" est une bonne chose, ici: cela signifie que vous pouvez vous exprimer avec le minimum de distraction de bas niveau (où de faible niveau est au niveau de la machine ou du niveau de la langue plutôt que du niveau de problème).
@Akashdeepsaluja - Salut. Cela passe simplement de la fin de la liste à l'avant, en train de vérifier que chaque élément de liste à l'avant correspond à celui correspondant à l'arrière. Le type peut-être a deux valeurs: rien ou juste (x), pour une certaine valeur x. Dans une langue moins civilisée, vous pouvez utiliser NULL ou NON-NULL. La fonction Q ne renvoie rien si cette liste n'est pas un palindrome.
@AkashdeepSaluja - Un moyen facile de comprendre ce que j'ai fait ci-dessus est que je comparais la liste source contre son inversion. S'ils correspondent, c'est un palindrome.
@RAFE Je pense que c'est une liste singulièrement liée et la traversée de l'arrière à l'avant n'est pas possible.
@AkashdeepSaluja - Sûr c'est. La méthode simple: calculez l'inversion de la liste et comparez-la à l'original. Ce que j'ai fait, c'est juste ceci, sauf que j'utilise la pile d'appels pour garder une trace de l'inversion plutôt que de le manifester physiquement en mémoire. Plus j'y pense, calculer réellement le renversement de la liste source semble être la meilleure option.
Étant donné que vous avez affaire à une liste liée , vous devez utiliser un peu d'espace supplémentaire ou beaucoup plus de temps supplémentaire.
Votre première approche semble raisonnable, mais vous pouvez déterminer la longueur de la liste et palindrome-ness en une seule fois.
Nous modifions la soi-disant algorithme de recherche de cycle de Floyd:
Si le pointeur rapide atteint la fin de la liste, le pointeur lent pointe vers le milieu de la liste, alors maintenant:
Un peu de travail supplémentaire est requis pour les listes avec un nombre impair d'éléments.
false )
Il est intelligent, mais il faut toujours une complexité supplémentaire et une complexité supplémentaire (N ^ 2) (vous devez vérifier tous les nœuds comme point de départ) - ce qui est similaire pour copier simplement la liste sur un tableau et faire des chèques
@izprgmr Je pense que le chef de la liste est donné, il n'y a donc qu'un seul point de départ et complexité O (n).
La complexité du temps et la complexité spatiale sont à la fois dans O (n). Vous iTERIE sur la liste exactement une fois et vous stockez exactement la moitié des éléments.
Philip: Votre approche est bien meilleure que la mienne. Merci :)
Puisque vous savez que la liste liée fait un cycle, et que vous recherchez uniquement des palindromes à la tête, vous pouvez faciliter la tâche de vous-même. Dans ce cas, commencez par un pointeur à la tête (appelez-le h) et un pointeur à la tête.LLEFT () (appelez-le t). Continuez maintenant à déplacer le pointeur de tête H à droite et le pointeur de la queue T au à gauche. Lorsque vous marchez la liste, vérifiez que les valeurs de ces éléments sont égales (c'est-à-dire un palindrome). Votre état d'arrêt prend cependant un peu plus. Il y a deux cas: Donc, vous vous arrêtez si h == t ou si h == (T.Right ()). Utilisation de cette approche (ou similaire) Vous visitez chaque élément une seule fois. Utilisez l'approche de tortue et de lièvre comme dans les autres solutions si vous ne savez pas si la liste liée est cyclique.
Votre solution serait bonne lorsqu'une liste est une liste doublement liée. Dans mon cas, cependant, je n'ai pas d'une telle installation. C'est une liste unique liée avec des pointeurs à des nœuds uniquement dans une direction.
Il suffit de coller ma mise en œuvre afin que nous puissions comparer avec chacun, complet test ici:
Je pense que nous n'avons pas besoin d'un espace supplémentaire pour cela. Et cela peut être fait avec O (n) complexité.
Modification de la solution de Philip:
Nous modifions la soi-disant algorithme de recherche de cycle de Floyd:
deux pointeurs, "lent" et "rapide", les deux commencent à la tête de la liste; Le pointeur lent avance un élément de liste par itération, le pointeur rapide deux éléments À chaque étape, le pointeur lent pousse l'élément actuel sur la pile Si le pointeur rapide atteint la fin de la liste, le pointeur lent pointe vers le milieu de la liste, alors maintenant:
Avoir un autre pointeur au début de la liste liée (Démarrer Pointre) et maintenant - Déplacez le pointeur de démarrage et le pointeur lent un par un et comparez-les - s'ils ne sont pas égaux, retournez faux - Si le pointeur lent atteint la fin de la liste, c'est un palindrome
Ceci est O (n) la complexité du temps et aucun espace supplémentaire n'est requis.
"Le pointeur lent pousse l'élément actuel de la pile" Cela ne nécessite pas plus d'espace? ...
Pourquoi la personne a-t-elle supprimé sa réponse qui avait une suggestion semblable à 2?
Voici ma question, vous souhaitez vérifier s'il contient un Palindrome à partir de la tête de la liste? ou le Palindrome peut-il commencer de tout nœud?
@ ST0LE Je pensais à un cas où le pallindrome commence à la tête. Ceci est un cas plus simple que celui où le pallindrome peut commencer à n'importe quel noeud (ou un problème où nous devons trouver le plus long pallindrome dans la liste)
Si vous pouvez utiliser une mémoire supplémentaire O (n), vous n'avez pas besoin d'algorithme de Floyd et vous n'avez besoin d'aucune intelligence exposée dans les réponses. Copiez simplement la liste sur un tableau et vérifiez si c'est un palindrome. Fait.