Reverse-Linked-List-Algorithmus

Question

Ich machte einen Algorithmus, der meine verknüpfte Liste umkehren sollte. Originalliste sieht wie 7 5 6 aus Ich möchte es auf 5 6 7 umkehren. Aber wenn die verknüpfte Liste nach der Reverse-Funktion ausdrucken Ich sehe nur 5

NodeType * temp = start; 
int dataHolder[length] = {0}; 
int runTime = length - 1; 

for(int i = 0; i<length; i++){ 
    if(temp->next == NULL){ 
     break; 
    } 

    dataHolder[runTime] = temp->data; 
    temp = temp->next; 
    runTime--; 
} 

for(int j = 0; j<length; j++){ 
    if(start->next == NULL){ 
     break; 
    } 

    start->data = dataHolder[j]; 
    start = start->next; 
} 

Answer 1

beiden Schleifen gedruckt werden, ein Element fehlt, Sie sollte iterieren, bis der aktuelle Knoten NULL ist, nicht bis der nächste Knoten ist. Tatsächlich können Sie diese Bedingung einfach in eine while-Schleife einfügen, anstatt eine for-Schleife zu verwenden, die für eine verknüpfte Liste logischer sein könnte (selbst wenn Sie die Länge bereits vorausberechnet haben). Auch ich vermute, dass Sie die gleiche start Variable verwenden, um das Ergebnis zu überprüfen, was nicht funktioniert, weil Sie es überschreiben. so etwas wie dieses versuchen:

NodeType * temp = start; 
int dataHolder[length] = {0}; 
int runTime = length - 1; 

while (temp != NULL) { 
    dataHolder[runTime] = temp->data; 
    temp = temp->next; 
    runTime--; 
} 

temp = start; 
runtime = 0; 
while (temp != NULL) { 
    temp->data = dataHolder[runtime]; 
    temp = temp->next; 
    runtime++; 
} 

Nachtrag:

Sie können tatsächlich eine verknüpfte Liste in O Reverse (n) ohne zusätzlichen Speicher mit (und ohne dass seine Länge vorauszuberechnen), nur durch Neuordnen die Zeiger. In einigen Fällen ist dies möglicherweise nicht akzeptabel (z. B. wenn Sie externe Zeiger oder Verweise auf Knoten haben, die erwarten, dass ihr Wert geändert wird, wenn Sie die Liste umkehren), aber meistens ist es in Ordnung. Es würde so etwas gehen:

NodeType * temp1 = start; // Assuming start is not NULL 
NodeType * temp2 = start->next; 
start->next = NULL; 

while (temp2 != NULL) { 
    NodeType * temp3 = temp2->next; 
    temp2->next = temp1; 
    temp1 = temp2; 
    temp2 = temp3; 
} 

Answer 2

Ihr Algorithmus funktioniert nicht, weil in der ersten Schleife Daten in dem ersten n-1 Knoten in das Array kopiert Dataholder und Kopieren Sie dann in der zweiten Schleife das Array in der Reihenfolge, in der Sie es abgerufen haben, in die verknüpfte Liste.

plus Sie bearbeiten Ihre Variable „Start“, die zu Beginn der Liste

am Ende der zweiten Schleife Startpunkte auf dem vorletzten Knoten in der Liste die einzige Referenz ist

und Sie die verknüpfte Liste angezeigt werden, die diese verwendet "Start" Variable

für Ihre eingegebenen Daten
7-> 5-> 6
nach dem 1. Schleifenverarbeitung in der Dataholder
Kopieren in die verknüpfte Liste. verlinkte Liste ist jetzt
7-> 5
aber beginnen zeigen auf 5

die verknüpfte Liste Anzeigen mit Start so offensichtlich 5 wird nur