Warum schlägt dieser Code eine doppelt verkettete Liste nicht um

Question

Ich habe versucht zu vermeiden, diese Frage hier zu stellen, aber nach fast einer Stunde mit Blick auf das gleiche Stück Code habe ich wirklich keine Ahnung, warum der folgende Code eine doppelt verknüpfte nicht umkehren kann Liste:

Node* Reverse(Node* head) { 
    if (head == nullptr) {return head;} 
    Node *iter = head, *tail, *newTail; 
    while (iter -> next != nullptr) {iter = iter -> next;} //to set the tail pointer 
    tail = iter; 
    newTail = tail; //the node that will become the tail after reversing is done 
    iter = head; 

    while (iter != tail) { 
     newTail -> next = iter; 
     iter -> prev = newTail; 
     newTail = iter; 
     iter = iter -> next; 
    } 

    newTail -> next = nullptr; 
    tail -> prev = nullptr; 
    return tail; 
} 

Ich würde jede Hilfe zu schätzen wissen.

BEARBEITEN Es scheint, dass der Code nichts mit dem zu tun hat, was ich vorhatte. Beeindruckend. Als Randnotiz habe ich nur den einführenden Programmierkurs absolviert, der keine Hinweise, geschweige denn verknüpfte Listen etc. enthält. Danke für Ihre Hilfe!

ENDGÜLTIGER CODE Wenn Sie interessiert sind, habe ich meinen Algorithmus zum Umkehren einer doppelt verketteten Liste beendet. Ich denke, es ist ein netter Ansatz, obwohl ich natürlich offen für Vorschläge bin.

Answer 1

In dem Code ist der newTail immer hinter dem iter. Innerhalb der While-Schleife ist newTail-> next auf iter und iter-> prev auf newTail gesetzt. Was hat keine Wirkung.

Vielleicht wird dieses Diagramm

helfen diese

Versuchen. Es durchläuft die Liste und tauscht für jeden Knoten den nächsten und vorherigen Zeiger aus. (Dies ist möglicherweise nicht der effizienteste Algorithmus.)

Node* Reverse2(Node* head) { 
    if (head == nullptr) {return head;} 
    Node *iter = head; 

    Node *tail = nullptr; 
    while (iter!=nullptr) { 
    tail = iter; //keep track of tail 

    Node *tmp = iter->next; //before swap, pre-fetch next node 

    swap(iter); 

    iter=tmp; //go to next node 
    } 

    return tail; 

} 

void swap(Node *n) { 
    Node *tmp = n->prev; 
    n->prev = n->next; 
    n->next = tmp; 
} 

Answer 2

Sagen wir, Sie haben 3 Elemente, nummerieren sie 0, 1, 2. Sie beginnen also mit newTail zeigt auf das letzte Element (2). Dann beginnst du von Anfang an (0) und stellst newTail->next = iter ein. Also jetzt 2 ist mit 0 verknüpft? Das klingt nicht so, als würde man die Liste umkehren.