Wie eine einfach verkettete Liste rückwärts lesen?

Question

Eine Methode, die ich denken kann, ist die Liste rückgängig zu machen und lesen Sie es dann. Aber dies beinhaltet die Liste zu ändern, die schlecht ist.
Oder ich kann eine Kopie der Liste machen und es dann umgekehrt, aber das nutzt zusätzliche 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

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

    Console.WriteLine(n.Data);

}

Answer 1

O (n) Speicher, und O (n) Leistung, erzeugt einen Stapel zu verwenden; schieben alles auf, wie Sie in Vorwärtsrichtung durchlaufen, dann ist alles Pop-off, die Ergebnisse ergibt.

O verwenden (n ^ 2) Leistung (aber O (1) zusätzlichen Speicher), lesen Sie es jedes Mal weiterleitet, bis der Knoten vor dem letzten Sie bekam.

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

Eines des Kennzeichens einer einfach verknüpften Liste ist, dass es in der Tat, einzeln verknüpft. Es ist eine Einbahnstraße, und es gibt keine Möglichkeit, das zu überwinden, wenn Sie es in etwas anderes (wie eine umgekehrt einfach verknüpften Liste, einen Stapel, eine doppelt verknüpfte Liste ...) drehen. Man muss sich auf die Natur der Dinge wahr sein.

Wie bereits darauf hingewiesen, früher; Wenn Sie eine Liste in beiden Richtungen zu durchqueren; Sie brauchen eine doppelt verknüpfte Liste haben. Das ist das Wesen einer doppelt verknüpften Liste, es geht in beiden Richtungen.

Answer 3

Wirklich sollten Sie eine doppelt verknüpfte Liste mit werden.

Wenn dies nicht möglich ist, glaube ich, die beste Wahl wird eine Kopie der Liste zu erstellen, die umgekehrt wurde.

Andere Optionen, wie unter Berufung auf Rekursion (effektiv Kopieren die Liste auf den Stapel) könnten Sie führen aus Stapelspeicherplatz laufen, wenn die Liste zu lang ist.

Answer 4

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

Answer 5

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 6

Es gibt eine dritte Lösung, diesmal mit O(log(n)) Speichern 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. Teilen Sie die Liste in zwei
2. Recurse in die zweite Hälfte der Liste
3. Drucken Sie den Wert in der Mitte
4. Recurse in der ersten Hälfte

Hier ist die Lösung in Python (ich weiß, C # nicht wichtig):

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)

Diese Neufassung statt Rekursion Iteration 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 7

Ihre einfach verknüpften Liste Unter der Annahme implementiert IEnumerable , Sie LINQ Methode Reverse-Erweiterung verwenden können:

var backwards = singlyLinkedList.Reverse();

Sie müssen eine using System.Linq; Direktive am Anfang der Codedatei hinzufügen LINQ-Erweiterungsmethoden zu verwenden.

Answer 8

Eine Variante einen Stapel zu erstellen und alle Elemente auf den Stapel schieben ist Rekursion zu verwenden (und das System ist in Stapel gebaut), dann ist dies wahrscheinlich nicht die Art und Weise mit der Produktion Code zu gehen, sondern dient als besser (IMHO) Interview Antwort aus den folgenden Gründen:

1. Es zeigt, dass Sie die Rekursion
Grok
2. Es ist weniger Code und erscheint elegantere
3. Ein naiver Interviewer kann nicht erkennen, dass es ein Raum-Overhead ist (wenn dies der Fall ist, möchten Sie vielleicht prüfen, ob Sie dort arbeiten wollen).

Answer 9

Nun würde die naive Lösung sein, den Überblick zu behalten, welche Knoten Sie sind momentan an, dann von Anfang an durchlaufen, bis Sie diesen Knoten finden, immer den Knoten Speichern Sie gerade verlassen. Dann wird jedes Mal, wenn Sie den Knoten finden Sie sich gerade an, erzeugen Sie den Knoten, den Sie gerade verlassen, speichert diesen Knoten als derjenige bist du gerade, dann wieder Iterierte von Anfang an.

Dies würde natürlich schrecklich schlechte Performance-weise sein.

Ich bin sicher, dass einige intelligentere 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 10

Das 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 11

Wenn in dem Explicit-Stack-Programm haben wir einen Stapel nur für die Daten von jedem Knoten erstellen (anstatt den Stack von Typ <Node> erstellen, erstellen wir Stapel Typ <T>) wäre es nicht noch besser sein? Weil wir nicht brauchen, dann andere Informationen des Knotens zu speichern.

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();
    }
}

Answer 12

Sie es in O lesen können (n ^ 2) - jedes Mal lesen, um den letzten Knoten gehen und aus dem vorherigen Drucken

Answer 13

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) Speicher und einfach wie do-re-mi!