Comment lire une liste de liens simples à l’envers?

Pour utiliser la mémoire O (n) et la performance O (n), créez une stack; poussez tout en itérant dans le sens suivant, puis enlevez tout pour obtenir les résultats.

Pour utiliser la performance O (n ^ 2) (mais la mémoire supplémentaire O (1)), lisez-la chaque fois, en remontant le noeud avant le dernier.

Exemple:

 IEnumerable Reverse (Node head) { Stack nodes = new Stack(); while(head != null) { nodes.Push(head); head = head.Next; } while(nodes.Count > 0) { yield return nodes.Pop().Value; } } 

L’une des caractéristiques d’une liste à lien unique est qu’elle est en fait liée à elle-même. C’est une rue à sens unique, et il n’y a aucun moyen de la surmonter à moins de la transformer en autre chose (comme une liste inversée à liens simples, une stack, une liste à double liens …). Il faut être fidèle à la nature des choses.

Comme cela a été souligné précédemment; si vous devez parcourir une liste dans les deux sens; vous devez avoir une liste doublement chaînée. C’est la nature d’une liste à double lien, elle va dans les deux sens.

En réalité, vous devriez utiliser une liste à double lien.

Si cela n’est pas possible, je pense que votre meilleure option sera de construire une copie de la liste qui a été inversée.

D’autres options, telles que le recours à la récursivité (copier efficacement la liste dans la stack), peuvent entraîner une saturation de l’espace de la stack si la liste est trop longue.

Si vous manquez de mémoire, vous pouvez inverser la liste, la parcourir et l’inverser à nouveau. Sinon, vous pouvez créer une stack de pointeurs sur les nœuds (ou tout ce qui ressemble à un pointeur en C #).

 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 } 

Il existe une troisième solution, utilisant cette fois la mémoire O(log(n)) et le temps O(n log(n)) , occupant ainsi le juste milieu entre les deux solutions de la réponse de Marc.

Il s’agit bien d’une descente inversée dans l’ordre d’un arbre binary [ O(log(n)) ], sauf que vous devez trouver le sumt de l’arbre [ O(n) ]:

1. Fractionner la liste en deux
2. Recurse dans la seconde moitié de la liste
3. Imprimer la valeur au milieu
4. Recurse dans la première moitié

Voici la solution en Python (je ne sais pas C #):

 def findMidpoint(head, tail): pos, mid = head, head while pos is not tail and pos.next is not tail: pos, mid = pos.next.next, mid.next return mid def printReversed(head, tail=None): if head is not tail: mid = findMidpoint(head, tail) printReversed(mid.next, tail) print mid.value, printReversed(head, mid) 

Cela pourrait être une refonte utilisant l’itération au lieu de la récursivité, mais au désortingment de la clarté.

Par exemple, pour une liste comportant des millions d’entrées, les trois solutions sont de l’ordre de:

 Performance de la mémoire de la solution
 ========================================
  Marc # 1 4MB 1 million d'opérations
   Mine 80B 20 millions d'opérations
  Marc # 2 4B 1 billion d'opérations

En supposant que votre liste à lien unique implémente IEnumerable , vous pouvez utiliser la méthode d’extension Reverse de LINQ:

 var backwards = singlyLinkedList.Reverse(); 

Vous aurez besoin d’append un using System.Linq; directive en haut du fichier de code pour utiliser les méthodes d’extension de LINQ.

Une variante de la création d’une stack et de l’ajout de tous les éléments sur la stack consiste à utiliser la récursivité (et la stack intégrée du système), ce n’est probablement pas la voie à suivre avec le code de production, mais constitue une meilleure réponse d’interview les raisons suivantes:

1. Cela montre que vous parlez récursion
2. C’est moins de code et semble plus élégant
3. Un intervieweur naïf peut ne pas se rendre compte qu’il y a un espace supplémentaire (si c’est le cas, vous voudrez peut-être déterminer si vous souhaitez travailler là-bas).

Eh bien, la solution naïve serait de garder trace du nœud auquel vous vous trouvez actuellement, puis effectuez une itération du début jusqu’à ce que vous trouviez ce nœud, en sauvegardant toujours le nœud que vous venez de quitter. Ensuite, chaque fois que vous trouvez le nœud sur lequel vous vous trouvez, vous créez le nœud que vous venez de quitter, enregistrez-le comme celui en cours, puis effectuez une nouvelle itération depuis le début.

Ce serait évidemment horriblement mauvais en termes de performances.

Je suis sûr que certaines personnes plus intelligentes ont une meilleure solution.

Pseudo-code (même avec des bugs):

 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 

C’est désordonné mais ça marche:

 class SinglyLinkedList { SinglyLinkedList next; int pos; SinglyLinkedList(int pos) { this.pos = pos; } SinglyLinkedList previous(SinglyLinkedList startNode) { if (startNode == this) return null; if (startNode.next == this) return startNode; else return previous(startNode.next); } static int count = 0; static SinglyLinkedList list; static SinglyLinkedList head; static SinglyLinkedList tail; public static void main (Ssortingng [] args) { init(); System.out.println("Head: " + head.pos); System.out.println("Tail: " + tail.pos); list = head; System.out.print("List forwards: "); while (list != null) { System.out.print(list.pos + ","); list = list.next; } list = tail; System.out.print("\nList backwards: "); while (list.previous(head) != null) { System.out.print(list.pos + ","); list = list.previous(head); } } static void init() { list = new SinglyLinkedList(0); head = list; while (count < 100) { list.next = new SinglyLinkedList(++count); list = list.next; } tail = list; } 

}

Si dans le programme Explicit Stack, nous créons une stack pour seulement les données de chaque nœud (au lieu de créer la stack de type , nous créons une stack de type ), ne serait-il pas encore meilleur? Parce que nous n’avons pas besoin de stocker d’autres informations du nœud à ce moment-là.

 IEnumerable Reverse (Node head) { Stack nodes = new Stack(); while(head != null) { nodes.Push(head.data); head = head.Next; } while(nodes.Count > 0) { yield return nodes.Pop(); } } 

vous pouvez le lire dans O (n ^ 2) – à chaque fois, allez au dernier noeud lu et imprimez le précédent

Quel est le problème avec:

  public void printBackwards(LinkedList sl){ ListIterator litr = sl.listIterator(sl.size()); Element temp; while(litr.previousIndex() >= 0){ temp = litr.previous(); System.out.println(temp); } } 

O (n) performance, O (1) mémoire et simple comme do-re-mi!