Traverse von einem Ende zum vorderen (C ++ LL Q: 1)

Question

---

int LinkedList::DoStuff()
{
Node *Current    = next_;
while ( Current != NULL )
    {
        Current = Current->next_;
        length_++;
    }
    // At the last iteration we have reached the end/tail/last node
    return length_;
}

---

gibt es keine weiteren Knoten über die letzte. Wie kann ich durchqueren zum Schwanzende an den Front-Kopf?

Answer 1

Rekursion kann arbeiten, wie es für jedes Element der ursprünglichen Liste eine Hilfsdatenstruktur, wie beispielsweise ein Array mit einem Eintrag zu bauen. Wenn Sie eine Lösung für eine Single-Threaded-Liste mögen, ohne O zu erfordern (n) zusätzliche Speicher, die beste Wette ist die Liste an Ort und Stelle umgekehrt wie Michael vermuten läßt. Ich schrieb ein Beispiel dafür, [aber ich werde es die Sorge um die Hausaufgaben gegeben auslassen]. Eine Warnung über die Liste Umkehrung: Wenn es irgendwelche andere Datenstrukturen, die Zeiger auf die ursprüngliche Liste zu halten, und Sie können sie während Ihres Traversal zugreifen, werden sie nicht funktionieren, wenn sie benötigen, um die Liste zuzugreifen, während es umgekehrt ist, und dies führen könnte, die Korruption zu Daten, wenn sie versuchen, die Liste zu ändern.

Update: Ok, hier ist die (C ++) Routine eine Liste an Ort und Stelle zu umkehren. Es wurde nicht, obwohl getestet. Und ich werde beachten Sie, dass, wenn diese Hausaufgaben sind, das Plakat immer noch herauszufinden, muss, wie diese Routine zu verwenden, korrekt eine vollständige Antwort zu erhalten.

Node *ReverseList(Node *head) {
    // Reverse a single-threaded list in place, return new head
    Node *prev=NULL;
    Node *cur=head;

    while (Node *next=cur->next_) {
        cur->next_ = prev;
        prev = cur;
        cur = next;
    }
    cur->next_ = prev;
    return cur;
}

Answer 2

Es sei denn, verknüpften Liste eine doppelt verknüpfte ist, dann ist dies schwer zu tun. Rekursion ist eine Möglichkeit, die Sie nicht so groß, haben Listen davon aus, dass Sie so (Pseudo-Code) aus Stapelspeicher, etwas laufen werden:

DoStuffBackwards (currNode) {
    if (currNode != NULL) {
        DoStuffBackwards (currNode->next);
        // Process currNode here.
    }
}

DoStuffBackwards (firstNode);

Das funktioniert, weil Sie für den nächsten Knoten Aufruf DoStuffBackwards() halten, bis die Liste erschöpft dann, wie Sie eine Sicherungskopie der Rekursion Stapel rollen Sie jeden Knoten verarbeiten.

Answer 3

Wenn Sie gerade nach hinten von den letzten Knoten zu aktuellen Knoten gehen wollen, als Pax Antwort (mit Rekursion) ist die beste Wahl, auch meine Version unten. Wenn Ihre aktuellen Knoten nicht der Kopf der nicht-kreis einfach verknüpften-Liste enthalten ist, und mögen, dass Sie von den aktuellen Knoten zu Knoten Kopf gehen, ist es unmöglich.

int LinkedList::DoStuff()
{
    return DoStuffBackward(next_, 0);
}

int LinkedList::DoStuffBackward(Node* node, int n)
{
    if (!node)
    {
        return n;
    }

    int len = DoStuffBackward(node->next_, n + 1);
    std::cout << "doing stuff for node " << n << std::endl;
    return len;
}

Answer 4

Dies hat den Geruch von Hausaufgaben, also keinen Code, aber hier ist eine Übersicht über eine Lösung, die nicht Rekursion erfordert:

Wenn Sie durch die Liste ausführen möchten rückwärts eine Option, um die Liste erneut zu verknüpfen, rückwärts zu zeigen, wie Sie es sind durchquert das Ende zu finden. Dann, wie Sie wieder Verfahrweg der Liste (die die Knoten in umgekehrter Reihenfolge aus der ursprünglichen Liste besucht) Sie Neuverknüpfung gleiche wie vorher, und die Liste endet in ihrer ursprünglichen Reihenfolge auf.

Das ist einfach im Konzept, aber die Zeiger und Links Handhabung richtig (besonders am Anfang und am Ende der Liste) kann ein wenig schwierig sein.

Answer 5

drücken Sie die Liste auf einem Stapel und dann knallen sie ab.

Answer 6

Ist verknüpften Liste Klasse doppelt verketteten oder einfach verknüpften? Wenn es keine zurück Zeiger in jedem Knoten, können Sie nicht rückwärts durchlaufen.

Ich schlage vor, Sie auch mehr Code schreiben und sich die Zeit nehmen, um Ihre Frage lesbar zu machen.