Seule liste liée dans java
je viens de trouver cette difficile question de l'entrevue en ligne, et j'espérais que quelqu'un pourrait m'aider à en comprendre le sens. C'est une question générique...étant donné une seule liste liée, swap de chaque élément de la liste de paires, de sorte que 1->2->3->4 devenir 2->1->4->3.
Vous devez permuter les éléments, mais pas les valeurs. La réponse devrait fonctionner pour la circulaire indique où la queue est pointant vers la tête de la liste. Vous n'avez pas à vérifier si la queue points à un niveau intermédiaire (sans en-tête) de l'élément.
Alors, j'ai pensé:
public class Node
{
public int n; //value
public Node next; //pointer to next node
}
Quelle est la meilleure façon de mettre en œuvre cette? Quelqu'un peut-il aider?
C'est une question d'entrevue, pas de devoirs? Intéressant.
Qu'est-ce que le downvote? C'est une question valable, et c'est intéressant aussi... upvoting.
OriginalL'auteur Simon Kiely | 2011-09-25
Vous devez vous connecter pour publier un commentaire.
Je suis d'accord avec @Stephen de ne pas donner la réponse (tout à fait), mais je pense que je devrais vous donner des conseils.
Une chose importante à comprendre est que Java n'a pas de spécifier de manière explicite des pointeurs plutôt, à chaque fois qu'un non-primitive (par exemple, ne pas
char
,byte
,int
,double
,float
,long
,boolean
,short
) est transmis à une fonction, il est passé comme une référence. Ainsi, vous pouvez utiliser des variables temporaires pour permuter les valeurs. Essayez de code un vous-même ou regarder ci-dessous:Alors vous aurez besoin d'une structure de données pour tenir le
Node
s. Il est important qu'il y ait un nombre pair deNode
s seulement (numéros impairs inutilement compliquer les choses). Il est également nécessaire d'initialiser les nœuds. Vous devez mettre ceci dans votre méthode principale.L'important est de définir le Nœud suivant les valeurs de. Vous ne pouvez pas simplement faire une boucle par un
for
boucle pour le tout, car alors le derniernext
jeter unIndexOutOfBoundsException
. Essayez de faire un vous-même, ou coup d'oeil à la mienne.Puis exécutez votre fonction d'échange sur eux avec un
for
boucle. Mais rappelez-vous, vous ne voulez pas exécuter sur chaque nœud... pensez-y un peu.Si vous ne pouvez pas le comprendre, voici mon code final:
J'espère que vous avez été capable de trouver au moins certains de ce avec d'orientation. Plus important encore, cependant, il est important que vous comprenez les concepts ici. Si vous avez des questions, laissez un commentaire.
Oui, vous avez raison à propos de complications. Cependant, il existe également de nombreuses interprétations du problème. Sera la dernière à être inchangée? Quel lien? À cause de cela (et que les chances n'étaient pas mentionnés dans la question), j'ai essayé de le simplifier afin de donner à la personne une idée générale de la façon d'aborder le problème. Pensez à cela comme un exercice pour lui. Je ne suis pas sûr de ce que vous entendez par "[h]ux sur une liste liée" - si vous faites allusion à l'
java.util.LinkedList
, j'essayais d'éviter que parce que c'est important d'en comprendre les rouages, mais oui, dans une situation réelle, il serait plus approprié.Non, je dis que vous n'avez pas besoin de tenir une liste liée dans un tableau, vous disposez déjà d'une liste liée.
OriginalL'auteur wchargin
Récursive Simple solution en Java:
OriginalL'auteur dareniott
Méthodes nécessaires à l'exécution de ce programme :
Approche est presque la même, d'autres tentent de les expliquer. Code de soi-même.
OriginalL'auteur mdev
Algo(nœud n1) -
garder 2 pointeurs n1 et n2, dans le courant de 2 nœuds. n1 --> n2 --->...
si(n1 et n2 sont liées les unes aux autres) retour n2;
si(n1 est NULL) return NULL;
si(n2 est NULL) return n1;
si(n1 et n2 ne sont pas liés les uns aux autres et ne sont pas null)
changer le pointeur de n2 à n1.
appeler le algorthm de manière récursive sur n2.prochaine
retour n2;
Code (de travail) en c++
}
OriginalL'auteur Nitin Garg
L'approche générale est à l'étape par le biais de la liste, et à chaque étape, vous réorganiser la liste des nœuds à l'affectation de la
node
valeurs.Mais je pense que vous aurez plus de cela (c'est à dire en savoir plus) si vous avez réellement concevoir, mettre en œuvre et tester vous-même. (Vous n'obtenez pas un "téléphone à un ami" ou "demandez DONC" lors d'un entretien d'embauche ...)
OriginalL'auteur Stephen C
Yep, écrivez un processus itératif de routine qui progresse de deux liens à chaque itération. Rappelez-vous le lien de l'itération précédente, de sorte que vous pouvez l'arrière-patch, puis permuter les deux liens. Les parties difficiles sont prise en main (dans une moindre mesure) et de savoir quand pour finir (pour les grands), surtout si vous finissez par avoir un nombre impair d'éléments.
OriginalL'auteur Hot Licks
J'ai écrit le code au niveau atomique. Donc, j'espère qu'il est auto-explicatif. Je l'ai testé. 🙂
OriginalL'auteur javaMan
OriginalL'auteur cHao
OriginalL'auteur Rocky
}
est pas valide). Troisième, où estlength
déclaré? Quatrième, qu'est-ce quelength1111
? Cinquièmement, même si ceux-ci sont corrigés, cela ne produira pas les résultats corrects.Et un autre -1 (dans l'esprit; je n'ai pas le cœur) parce que ce qui est le tableau?
sinon, comment voulez-vous parcourir les Nœuds sans les placer dans une structure de données comme un tableau
Merci de ne pas insulter mon intelligence. Je comprends au sujet de votre problème matériel, et j'apprécie le fait que vous voulez aider. Cependant, se rendre compte qu'un downvote est une occasion d'apprendre - essayer d'intégrer cela dans votre prochaine réponse, peut-être.
C'est une liste liée, en suivant les pointeurs; c'est la façon dont ils travaillent. Certaines langues n'ont pas de tableaux--comment voulez-vous le faire dans l'un de ces? (Personnellement, j'ai trouvé le code un peu opaque, et j'ai un peu d'intelligence 🙂
OriginalL'auteur Andrew Briggs