Une méthode que je peux penser est d'inverser la liste, puis de la lire.
Mais cela implique de changer la liste qui est mauvaise.
Ou je peux faire une copie de la liste, puis inverser, mais cela utilise une mémoire supplémentaire O (n).
Existe-t-il une meilleure méthode qui n'utilise pas de mémoire supplémentaire et ne modifie pas la liste et ne fonctionne pas dans O (n) Time
Le code de liste lié inverse est quelque chose comme ceci en C # solution récursive est
13 Réponses :
Eh bien, la solution naïve serait de garder une trace de laquelle le nœud que vous êtes actuellement à l'heure actuelle, puis d'itérer dès le début jusqu'à ce que vous trouviez ce nœud, sauvegarde toujours le nœud que vous venez de rester. Ensuite, chaque fois que vous trouvez le nœud que vous avez actuellement, vous produisez le nœud que vous venez de rester à gauche, enregistrez ce nœud comme celui que vous êtes actuellement à l'heure actuelle, puis réémarez-la du début.
Ce serait bien sûr horriblement horriblement Mauvaise performance-sage. P>
Je suis sûr que certaines personnes plus intelligentes ont une meilleure solution. p>
pseudo-code (avec des bugs même): p>
current node = nothing
while current node is not first node
node = start
while node is not current node
previous node = node
node = next node
produce previous node
set current node to previous node
Vous pouvez le lire dans O (n ^ 2) - Chaque fois que vous allez sur le dernier nœud, lisez et imprimez le précédent
Vraiment, vous devriez utiliser une liste doublement liée.
Si ce n'est pas possible, je pense que votre meilleure option sera de construire une copie de la liste inversée.
Autres options, telles que compter sur la récursivité (copier efficacement la liste sur la pile) pourraient vous faire sortir de l'espace de pile si la liste est trop longue.
Voir tag - "Interview-questions" :)
Je pense que la modification de la liste en une liste doublement liée est moins mauvaise que d'autres mécanismes pour résoudre le problème.
utiliser o (n) performance de la mémoire et O (n), créez une pile; Poussez tout ce que vous ithérlez dans la direction de l'avant, puis tout éteint, cédant les résultats.
utiliser o (n ^ 2) performance (mais O (1) de mémoire supplémentaire), lisez-la à chaque fois, le Le nœud avant le dernier que vous avez arrivé.
exemple:
Cela équivaut à créer une copie inversée de la liste.
C'est une meilleure solution, mais elle utilise la même mémoire O (n), identique à celle d'avoir une copie de la liste et de l'annuler et de la lire
Pas nécessairement. Vous devez seulement pousser les pointeurs sur la pile, pas les éléments entiers.
Ceci est fondamentalement identique à la récursion. La seule différence est une pile explicite contre la pile implicite de la réursion.
Avec la récursion, vous devez également pousser également l'état supplémentaire représentant la position d'appel. L'utilisation d'une pile explicite est généralement plus efficace.
@Marc par "Position d'appel" Vous signifie probablement "Adresse de retour"?
La combinaison de l'adresse de retour et de l'adresse suivante du nœud, en fonction de la mise en œuvre.
Si vous êtes à la mémoire de la mémoire, vous pouvez renvoyer la liste, itérairez-le et reverrez à nouveau. Sinon, vous pouvez faire une pile de pointeurs à des nœuds (ou tout ce qui est comme un pointeur en C #).
L'une des caractéristiques d'une liste individuellement liée est qu'elle est en fait liée. C'est une rue à sens unique, et il n'ya aucun moyen de surmonter que si vous le transformez en autre chose (comme une liste lié inversée, une pile, une liste doublement liée ...). Il faut être fidèle à la nature des choses.
Comme il a été souligné plus tôt; Si vous avez besoin de traverser une liste des deux manières; Vous devez avoir une liste doublement liée. C'est la nature d'une liste doublement liée, il va dans les deux sens.
+1 soupir. Pourquoi la simplicité est-elle défendue par ceux qui l'ont construite, alors vérité en vérité?
Ceci est désordonné mais fonctionne: }
En supposant que votre liste individuelle implémente implémente iEnumerable var backwards = singlyLinkedList.Reverse();
... ce qui est exactement ce que l'OP a suggéré mais voulait une meilleure solution que. Juste parce que vous n'allouez pas vous-même que vous ne comprenez pas vous-même que cela ne signifie pas que cela n'arrive pas.
L'inverse est chargé paresseusement, exécuté lorsque les éléments sont demandés. Ce n'est pas la même chose que l'OP.
une variante de la création d'une pile et de repousser tous les éléments sur la pile consiste à utiliser la récursion (et la pile intégrée du système), ce n'est probablement pas le moyen d'accéder au code de production mais sert d'interview meilleur (IMHO) Réponse pour les raisons suivantes:
Il y a une troisième solution, cette fois en utilisant Il est efficacement une descente inverse dans l'ordre d'un arbre binaire [ Voici la solution en python (je ne sais pas c #): Ceci pourrait être reflété à l'aide de l'itération au lieu de la récursivité, mais à la Coût de la clarté. Par exemple, pour une liste de million d'entrée, les trois solutions prennent de l'ordre de: O (journal (n)) mémoire et O (n journal (n)) temps, occupant ainsi le terrain du centre entre les deux solutions de la réponse de Marc. O (journal (n)) ], sauf à chaque étape, vous devez trouver le haut de l'arbre [ O (n) ]:
@chrispy: Un arbre avec n nœuds a besoin o (n) mémoire et non o (log n) comme vous l'avez mentionné. Ai-je compris quelque chose de mal?
@eskay Le code traverse la liste comme si Il y avait un arbre associé, ne crée pas l'arbre en mémoire
@Lazer: ignorer le mot "arbre" et penser en termes de division et de conquérir: Si vous gardez une trace du point de mi-chemin, vous pouvez traiter la seconde moitié de la liste aussi efficacement que la première moitié. Lors du traitement de la première seconde de la liste, si vous gardez une trace du point 3/4, vous pouvez traiter les quatre trimestres aussi rapidement que le troisième trimestre. Ensuite, lors du traitement de la première moitié, conservez le point 1/4 afin que vous puissiez traiter le deuxième trimestre aussi efficacement que le premier.
Qu'est-ce qui ne va pas avec: o (n) performance, o (1) mémoire et simple comme do-re-mi!
Down voté; La liste liée au C # est implémentée sous forme de liste doublement liée et le PO demande une liste lié individuellement liée.
void reverse_print(node *head)
{
node *newHead = NULL, *cur = head;
if(!head) return;
// Reverse the link list O(n) time O(1) space
while(cur){
head = head->next;
cur->next = newHead;
newHead = cur;
cur = head;
}
// Print the list O(n) time O(1) space
cur = newHead;
while(cur) {
printf(" %d", cur->val);
cur = cur->next;
}
// Reverse the link list again O(n) time O(1) space
cur = newHead;
while(cur){
newHead = newHead->next;
cur->next = head;
head = cur;
cur = newHead;
}
// Total complexity O(n) time O(1) space
}
Meilleur algo pour l'impression inverse, économise du temps et de l'espace
Si dans le programme de pile explicite, nous créons une pile pour que les données de chaque nœud (au lieu de créer la pile de type
Récursion est votre ami
@Neil: Pouvez-vous suggérer un pseudo code à l'aide de la récursion
Mais la récursion utilise une mémoire O (n)
Des réponses ci-dessous, nous pouvons résoudre ce problème dans O (n) Temps que si nous utilisons O (n) de mémoire supplémentaire. Voir les réponses ci-dessous .... merci les gars pour toute l'aide .... c'est vraiment génial et vous gars rock !!! ....
Neil: Vérifiez ma mise en œuvre récursive
La récursion utilisera toujours O (n) de mémoire supplémentaire. Événement pire, c'est la mémoire de pile, que vous n'avez généralement pas beaucoup de.