Wie liest man eine einfach verkettete Liste rückwärts?

Question

Eine Methode, die ich mir vorstellen kann, besteht darin, die Liste umzukehren und sie dann zu lesen. Aber das beinhaltet die Änderung der Liste, die schlecht ist.
ODER Ich kann eine Kopie der Liste machen und sie dann umkehren, aber das verwendet zusätzlichen O (n) Speicher. Gibt es eine bessere Methode, die keine zusätzlichen Speicher nicht verwendet und verändert nicht die Liste und läuft in O (n) Zeit

Reverse-Linked-List-Code ist so etwas wie dies in C#

Void Reverse (Node head) 
{ 
    Node prev= null; 
    Node current = head; 
    Node nextNode = null; 

     while (current!=null) 
     { 
      nextNode = current.Next; 
      current.Next = prev; 
      prev=current; 
      current = nextNode; 

     } 
     head = prev; 

} 

rekursive Lösung ist

void ReadBackWard (Node n) 
{ 
    if (n==null) 
     return; 
    else 
     ReadBackward(n.Next); 

    Console.WriteLine(n.Data); 

} 

Answer 1

Um O (n) Speicher und O (n) Leistung zu verwenden, erstellen Sie einen Stapel; pushen Sie alles vorwärts, während Sie in Vorwärtsrichtung iterieren, und geben Sie dann alles aus, um die Ergebnisse zu erhalten.

Um O (n^2) Leistung (aber O (1) zusätzlichen Speicher) zu verwenden, lesen Sie es jedes Mal vorwärts, bis der Knoten vor dem letzten, den Sie bekommen haben.

Beispiel:

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

Answer 2

Nun würde die naive Lösung zu verfolgen sein, welcher Knoten Sie sind momentan an, dann von Anfang an durchlaufen, bis Sie diesen Knoten finden, immer den Knoten Speichern Sie gerade verlassen. Jedes Mal, wenn Sie den Knoten finden, an dem Sie sich gerade befinden, erstellen Sie den Knoten, den Sie gerade verlassen haben, speichern diesen Knoten als den Knoten, auf dem Sie sich gerade befinden, und wiederholen ihn von Anfang an.

Dies wäre natürlich schrecklich schlecht in Bezug auf die Leistung.

Ich bin sicher, dass einige klügere Menschen eine bessere Lösung haben.

Pseudo-Code (mit Fehlern selbst):

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 

Answer 3

Sie es in O lesen können (n^2) - jedes Mal auf den letzten Knoten gelesen gehen und ausdrucken den vorherigen

Answer 4

Wirklich sollten Sie eine doppelt verknüpfte Liste verwenden.

Wenn dies nicht möglich ist, denke ich, Ihre beste Option wird es sein, eine Kopie der Liste zu erstellen, die umgekehrt wurde.

Andere Optionen, z. B. die Verwendung von Rekursion (effektives Kopieren der Liste auf den Stapel), können dazu führen, dass Ihnen der Stapelspeicher ausgeht, wenn die Liste zu lang ist.

Answer 5

Wenn Sie Speicher kurze Sie Liste rückgängig machen kann, über sie durchlaufen und es wieder umkehren. Alternativ können Sie einen Stapel Zeiger auf Knoten (oder was auch immer wie ein Zeiger in C# ist) machen.

Answer 6

Eines der Kennzeichen einer einfach verknüpften Liste ist, dass sie tatsächlich einzeln verknüpft ist. Es ist eine Einbahnstraße, und es gibt keine Möglichkeit, das zu überwinden, es sei denn, Sie verwandeln es in etwas anderes (wie eine umgekehrte einfach verknüpfte Liste, einen Stapel, eine doppelt verknüpfte Liste ...). Man muss der Natur der Dinge treu sein.

Wie bereits erwähnt; wenn Sie eine Liste in beide Richtungen durchlaufen müssen; Sie müssen eine doppelt verknüpfte Liste haben. Das ist die Natur einer doppelt verknüpften Liste, es geht in beide Richtungen.

Answer 7

Dies ist chaotisch, aber funktioniert:

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 (String [] 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; 
} 

}

Answer 8

Angenommen, Ihre einfach verknüpften Liste IEnumerable implementiert <T>, können Sie LINQ Reverse-Extension-Methode verwenden:

var backwards = singlyLinkedList.Reverse(); 

Sie Es muss eine using System.Linq; Direktive oben in der Codedatei hinzugefügt werden, um die LINQ-Erweiterungsmethoden zu verwenden.

Answer 9

Eine Variante des Erstellens eines Stapels und des Schiebens aller Elemente auf den Stapel ist die Rekursion (und der eingebaute Stack des Systems), dies ist wahrscheinlich nicht der Weg zum Produktionscode, sondern dient als besser (IMHO) Interview Antwort aus den folgenden Gründen:

1. Es zeigt, dass Sie weniger Code Rekursion
2. Es ist grok und erscheint elegante
3. eine naive Interviewer kann nicht erkennen, dass es ein Raum Overhead ist (wenn dies der Fall ist Vielleicht möchten Sie überlegen, ob Sie dort arbeiten wollen.

Answer 10

Es gibt eine dritte Lösung, diesmal mit O(log(n)) Speicher und O(n log(n)) Zeit, also den Mittelweg in Marcs Antwort zwischen den beiden Lösungen einnimmt.

Es ist effektiv ein Reverse in Ordnung Abstieg eines binären Baumes [O(log(n))], außer dass Sie bei jedem Schritt müssen die Spitze des Baumes finden [O(n)]:

1. Split die Liste in zwei
2. Recurse in die zweite Hälfte der Liste
3. drucken der Wert am Mittelpunkt
4. Recurse in die erste Halb

Hier ist die Lösung in Python (ich weiß nicht, 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) 

Dieses statt Rekursion Iteration neu gefasst werden könnte, aber auf Kosten der Klarheit.

Zum Beispiel für eine Million-Meldeliste, die drei Lösungen nehmen in der Größenordnung von:

 
Solution Memory  Performance 
========================================= 
MarC#1  4MB 1 million operations 
    Mine  80B 20 million operations 
MarC#2  4B 1 trillion operations 

Answer 11

Was ist los mit:

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

O (n) Leistung, O (1) Erinnerung und einfach wie do-re-mi!

Answer 12

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 
} 

Answer 13

Wenn in der Explicit-Stack-Programm haben wir einen Stapel nur für die Daten von jedem Knoten erstellen (statt der Schaffung der Stapel <Node> Art schaffen wir Stapel vom Typ <T>) wäre es nicht noch besser sein? Weil wir dann keine anderen Informationen des Knotens speichern müssen.

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