Mettre en œuvre un algorithme d'insertion d'un nœud dans une circulaire de la liste liée, sans le traverser
Je pensais à une solution à ce problème.
Mon entrée:
1. Une queue pointeur qui pointe vers le dernier nœud.
2. Une fois que vous savez le dernier pointeur vous pouvez facilement ajouter un nouveau nœud à côté d'elle.
Void Insert(Node N)
{
if (head == null) //linked list is empty
{
head = N; tail = N; tail.Next = head;
}
else
{
Node temp = tail.Next; //since this is circular tail will point to head
Tail.Next = N;
N.Next = temp; //correct
tail = N;
}
}
Any1 peut imaginer une meilleure solution sans l'aide de la queue de pointeur? Aussi, comme indiqué dans le problème sans le traverser?
C'est une question d'entrevue, juste besoin de quelques entrées pour trouver la meilleure solution.
où est le point d'insertion?
après le dernier nœud
Il y a un bug là, je crois qu'il devrait être N. Next = temp. En dehors de cela, il me semble une très bonne façon de faire les choses...
Hey Jaime, merci pour la capture de l'insecte. J'ai édité mon code
après le dernier nœud
Il y a un bug là, je crois qu'il devrait être N. Next = temp. En dehors de cela, il me semble une très bonne façon de faire les choses...
Hey Jaime, merci pour la capture de l'insecte. J'ai édité mon code
OriginalL'auteur Learner | 2009-07-08
Vous devez vous connecter pour publier un commentaire.
Je suppose que vous avez un seul liés circulaire de la liste, et seulement un pointeur vers un élément (appelons cela le nœud de tête). Chaque nœud de la liste comprend donc une valeur et un pointeur vers l'élément suivant. La queue points de nœud à la tête de nœud. L'insertion d'un nœud directement après le nœud de tête est trivial. Je suppose que vous voulez insérer un nœud directement avant la tête de nœud. Pour cela, vous devez le nouveau nœud à devenir le dernier nœud, ce qui est fait à partir de l'ancien dernier nœud, et qui pointe vers le nœud de tête. Maintenant, vous voulez éviter la traversée de la liste pour découvrir le dernier nœud. Cela signifie que vous ne pouvez pas accéder à ce dernier nœud et donc, de ne pas modifier son pointeur. La seule autre façon de faire de ce travail est de modifier le lieu que les derniers points de nœud, c'est à dire:
OriginalL'auteur Svante
vous avez également la tête de nœud. vous pouvez insérer utilisation trop. Je suis en supposant que il n'y a pas de restriction sur l'endroit où insérer le nouveau nœud (question de ne pas spécifier explicitement que).
De l'insérer sur la tête, est trivial.
Modifier Insérer après le chef
yaa je suis d'accord, mais, fondamentalement, que non pas ce que le recruteur vous attendent
gud point, dans ce cas, l'insertion au 2ème nœud ne
avec Oumayr idée que je peux insérer, après la tête, mais ce n'est pas ce que nous recherchons
J'ai besoin de l'insérer à la fin, si l'insertion, après la tête habitude suffire
OriginalL'auteur Umair Ahmed
Si votre mesure de "mieux" est de ne pas maintenir à la fois la tête et la queue des pointeurs, vous pouvez simplement mettre à jour l'indicateur de queue. La tête du pointeur est implicite (donné par la queue.À côté).
Dans la pratique, l'accès à une liste est souvent assez commun (dites si vous êtes à l'aide de la circulaire, la liste d'attente), et d'avoir une étape supplémentaire pour accéder à la tête peut ajouter des frais généraux. Dans un test pour un projet que j'ai fait, en éliminant la tête de pointeur de cette manière, abaissé la mémoire de certains (nos listes ont été généralement courte, mais nous avons eu beaucoup d'entre eux), mais le temps a augmenté depuis que nous avons souvent accédé à la tête de la liste. YMMV.
OriginalL'auteur Zayenz
Non, vous avez besoin de la queue de pointeur. Sinon, vous devrez parcourir la liste. Sinon, comment voulez-vous savoir où la fin de la liste.
Vous pourriez en venir à une sorte de intelligent de l'indexation de l'arithmétique, mais ce serait toujours un pointeur sur la tête/queue.
OriginalL'auteur Robert Harvey
J'ai simplifié votre code un peu. Pas besoin de le temp variable, vous n'avez même pas l'utiliser pour quoi que ce soit après l'avoir définie.
OriginalL'auteur Lars Haugseth
Au lieu de stocker la tête et la queue, juste stocker la queue.
OriginalL'auteur Craig Gidney