En interview m'a demandé de trouver la valeur dans le 2e noeud du nœud moyen de la liste liée? Ils s'attendaient à le faire dans une complexité de temps O (n).
J'ai essayé de donner la réponse à obtenir l'élément moyen à l'aide de O (N2). Mais cela ne pouvait pas aider grand chose. Puis essayé de faire dans O (n) en utilisant des pointeurs lents et rapides.
nœud lent, rapide; 1 2 3 4 5 6 7 8 9
Noeud de sortie: parce que le nœud moyen est 7 5 et 2ème élément de celui-ci est 7 . < p> Les solutions sont très appréciées.
4 Réponses :
Une des solutions pourrait être:
.
- Lorsque vous touchez la fin de la liste liée, recherchez l'index (
i ) de l'élément du milieu en fonction de la taille de la liste.
- incrémente cet index par 2 (
i + 2 ).
- Suivez la référence de la liste à l'index
i + 2
- vous avez l'élément.
Une autre solution pourrait être d'itérer directement la liste liée si vous avez une variable qui contient la taille de la liste liée.
moyenplustwo )
- Itéréez la liste liée et faites un compteur.
- arrêtez-vous lorsque le compteur est égal à
Midplustwo
Node getSecondAfterMind(Node head) {
Node slow = head, fast = head;
while(fast.next.next != NULL) {
slow = slow.next;
fast = fast.next.next;
}
if slow.next!= NULL && slow.next.next != NULL {
return slow.next.next;
}
return NULL;
}
L'approche consiste à trouver le nœud au milieu de la liste liée à l'aide de la méthode de pointeur lente rapide. Ensuite, il suffit de trouver le nœud suivant du prochain nœud du noeud moyen.
De cette façon, vous pouvez obtenir le noeud requis dans O (1) espace et o (n) complexité de temps.
@ Sourabh1024 a écrit le code. Jetez un coup d'œil.
Bienvenue sur Stack Overflow .. Montrez d'abord ce que vous avez essayé ... Où est votre code, puis demandez ce que vous voulez?