benachbarte Knoten in einer verknüpften Liste (iterativer Ansatz) Swapping

Question

Frage Erklärung: Ich habe wie diese benachbarte Paare tauschen:
Eingang: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
Ausgabe: 2 -> 1 -> 4 -> 3 -> 5 -> NULL
Dieser Code gibt einen Segmentierungsfehler. Außerdem möchte ich wissen, ob diese Logik korrekt ist oder nicht?

listnode* swapPairs(listnode* head) { 
    /* corner cases not included, don't bother */ 
    listnode *prev = head; //points to first node 
    listnode *curr = prev -> next;  //points to second 
    head = curr; //displacing head to the second element of list 
    listnode *next;  //points to next of second 
    while(curr != NULL || prev != NULL) { 
     next = curr -> next;  
     curr -> next = prev; 
     prev -> next = next; 
     prev = next; 
     curr = prev -> next; 
    } 
    return head; 

Answer 1

Es gibt mehrere Probleme, die Sie nicht überprüfen, ob head oder head->next NULL sind. Dann überprüfen Sie nicht, ob curr = prev -> next; NULL ist, was ein Problem ist, wenn die Anzahl der Knoten nicht gerade ist.

Trotzdem ist der Algorithmus fehlerhaft, der erste Austausch ist korrekt, aber jeder nachfolgende wird fehlschlagen, weil der Knoten, der auf den ersten Knoten zeigt, von den beiden, die ausgetauscht werden, nicht aktualisiert wird.

Ich schlage vor, Sie tauschen die Werte der Knoten, die viel einfacher ist, wie die Mitglieder next müssen nicht geändert werden.

Answer 2

Zunächst einmal ist es nicht nötig, die Verbindung zu ändern, tauschen Sie einfach den Wert dieses Knotens mit dem nächsten Knoten.Weil nach Ihrer Frage müssen Sie nur den Wert und nicht den Knoten tauschen, also denke ich nicht ändern Link wäre eine gute Idee, also würde ich Ihnen empfehlen, nur den Wert des Knotens zu tauschen und dann sind Sie gut zu gehen.

Answer 3

Wenn die Anforderung verbietet nur die benachbarten Werte zu tauschen (das ist viel einfacher zu tun, weil es keine Bruch oder eine neue Bindungsbildung zwischen den Knoten benötigt), und will stattdessen die tatsächlichen benachbarten Knoten zu vertauscht werden, müssen Sie beachten Sie die Schwanz der zuletzt vertauschten benachbarten Knoten die ganze Zeit.

listnode* swapPairs(listnode* head) { 
    listnode *prev = head;  
    listnode *curr; 
    listnode *next = null, *tail = null;  
    while(prev != null && prev->next != null) { 
     curr = prev->next; 
     next = curr->next;  
     curr->next = prev; 
     if(tail != null) tail->next = curr; 
     else head = curr; //First two nodes are swapped. First node (previously second node) will be new head 
     tail = prev;  //Tail of lastly swapped nodes i.e. previously first one of them 
     prev = next;  //Swapping done between curr and pre, now move to next node 
    } 
    if(tail != null) { 
     tail->next = next; 
    } 
    return head; 
}