La suppression d'un nœud à partir d'une seule liste, lorsque seulement le pointeur vers le nœud donné
C'est une question que je me posais dans une interview.
"Une seule liste, il y a dans la mémoire. Vous devez supprimer un nœud. Vous avez besoin d'écrire une fonction pour supprimer ce nœud, qui ne prend que l'adresse du nœud d'être supprimé, comme l'entrée et rien d'autre(y compris la tête)"
J'ai donné la réponse similaire à celle de réponse ci-dessous post -- Copier le contenu du nœud suivant dans le nœud à supprimer et supprimer le suivant.
Mais l'interviewer a demandé de nouveau de moi, ce que si je passe l'adresse du dernier nœud. Je lui ai dit que, depuis que le prochain sera un NULL, copiez cette valeur NULL dans le champ de données ainsi que l'adresse vers le nœud suivant, qui est également NULLE. Puis il m'a dit il y aura un problème de pendre des pointeurs... que je n'ai pas comprendre un peu. Peut quelqu'un s'il vous plaît jeter la lumière sur ce problème ? Est-il un générique solution ?
Mise à jour (Deux jours plus tard) : Un petit peu plus. Vu qu'il n'y est pas de nœud spécial à la fin de la liste. Et le dernier nœud points à NULL et si ce nœud est donnée en entrée, comment faire de l'avant-dernier point de nœud à NULL. Ou est-ce impossible ?
Il suffit de mettre : Si un nœud est donnée en entrée à une fonction, comment faire le pointeur de la référence, du point de NULLE
Les deux, en fait je veux savoir à propos balançant pointeur aussi..
OriginalL'auteur King | 2012-02-20
Vous devez vous connecter pour publier un commentaire.
Balançant Pointeur:
Dans votre réponse, pour supprimer le nœud que vous avez fait de supprimer les prochaine nœud, ce qui peut être référencé par un pointeur. C'est la façon bancale pointeur en cas de problème.
(1) Il n'existe pas en dehors des références à la liste, comme vous le préciser dans une note.
(2) Bancales pointeur problème peut se poser, que l'intervieweur dit.
À la fois (1) et (2) ne peut pas être correcte à la fois. Ce qui signifie qu'il y a un malentendu quelque part.
À propos de la Suppression du Dernier Nœud:
Je pense que vous confondez deux choses: (1) Un pointeur p qui pointe vers NULL, (2) UNE liste liée nœud qui a la valeur NULL dans son champ de données.
Supposons que la structure de données est
a -> b -> c -> d
. Écrit NULLE à d du champ de données ne sera pas magicly faire c d'avoir un pointeur NULL dans sonnext
champ.Vous pouvez supprimer le dernier nœud si la liste liée a toujours un spécial dernier nœud qui ne sera jamais supprimé. Par exemple,
a -> b -> c -> d -> LAST
DERNIER a une valeur particulière dans son champ de données qui indique qu'il est vraiment le dernier élément. Maintenant pour supprimer d, vous pouvez supprimer la DERNIÈRE et écrire la valeur spéciale en d du champ de données.Peut-être que ce sont exactement ce que vous avez essayé de dire au cours de l'entrevue, auquel cas il doit y avoir un malentendu entre vous et le recruteur.
c'est ma réponse à la mise à jour de votre question: c'est impossible. Vous devriez peut-être poster une nouvelle question si vous voulez un deuxième avis.
OriginalL'auteur Ali Ferhat
Suit:
Fonction:
OriginalL'auteur Saket Vatsa
puis il devrait y avoir un chèque d'un programme si le nœud donné est le dernier nœud ou pas.
OriginalL'auteur hallah shahid butt
Si il y a d'autres éléments qui pointent vers le nœud suivant qui sera copié vers le nœud actuel, puis supprimé, puis cette opération permettra d'introduire un bug. Donc, dans votre réponse, vous devriez avoir souligné que votre solution ne fonctionne que si il n'y a pas des références extérieures à la liste.
Votre solution fonctionne avec le dernier nœud que si la structure de données est augmentée avec un "noeud" de l'élément. (Si vous utilisez Smalltalk, vous pouvez écrire
self become: nil
Aucune autre langue a quelque chose de semblable)Non, il n'existe pas de solution générique si il y a des références extérieures à la liste. Je pense que l'intervieweur voulais voir si vous êtes vraiment compétent dans le sujet ou l'ont été il suffit de répéter un mémorisé réponse.
OriginalL'auteur Ali Ferhat
Probablement votre liste de liens traversant pourriez avoir besoin de supposer que tout nœud qui points à
null
estnull
nœud, indépendamment de la valeur...donc
d
estnull
nœud et le nœud ne doit pas être considéré comme un nœud. de cette façon, vous pouvez économiser sur l'utilisation des valeurs spéciales, puisqu'elles ne sont pas correctes dans un sens générique. d'autres que vous n'aurez pas d'autre moyen pour le nœud précédent à point ànull
.OriginalL'auteur nitsi
OriginalL'auteur sreeprasad