Wie in einer verknüpften Liste

Question

void delete_double (LN<T>*& l) { 
    if (l == nullptr) 
     return; 

    LN<T> *p = l; 
    while (p -> next != nullptr && p -> next -> next != nullptr) 
    { 
     if (p -> value == p -> next -> value) // the current value is equal to the next value in the linked list 
     { 
      if (p == l)      // when the first two values are the same          // not sure if it is correct 
      { 
       l = l -> next -> next; 
      } 
      else       // Problem should be here 
      { 
       LN<T> *to_delete = p;  // Also tried this (doesn't work) 
       p = p->next; 
       delete to_delete;   // LN<T>* to_delete = p; 
              // LN<T>* to_delete2 = p -> next; 
       LN<T> *to_delete1 = p;  // l = to_delete2 -> next; 
       p = p->next;    // delete to_delete; 
       delete to_delete1;   // delete to_delete2; 
      } 
     } 
     else 
     { 
      p = p-> next; 
     } 
    } 
} 
// Image below is my output 

enter image description here

Hallo zwei Elemente in einer Zeile zu löschen, ich eine Funktion schreibe, die zwei Werte in einer Zeile in einer verknüpften Liste löschen, wenn die beiden Werte gleich sind. Mein Code scheint nicht mehr zu funktionieren, wenn die Eingabe etwas wie "1 -> 2 -> 3 -> 3 -> 4 -> nullptr" ist (die Ausgabe sollte 1 -> 2 -> 4 -> nullptr sein). Es wird beendet, ohne mir einen Fehler zu geben. Und ich ging Zeile für Zeile durch das Debugging, es kommt plötzlich und zeigt "Variablen sind nicht verfügbar".

Ich vermute, es ist das Problem, dass, wenn ich p löschen, l auf Müll zeigt, was das Problem verursacht. Also habe ich einen anderen Weg ausprobiert, um auf to_delete -> next zu zeigen. Aber es funktioniert immer noch nicht.

Ich habe so viele Stunden versucht, es zu beheben und das Debug wird nicht einmal helfen. Kann mir bitte jemand helfen? Ich danke dir sehr!

Answer 1

Ich habe den Code oben vereinfacht, die Logik, die Sie oben haben, wird Ihnen auch nicht helfen, mehrere Duplikate zu entfernen. Also schauen wir uns die nachfolgenden Code und sezieren:

void delete_double(LN<T>*& l) { 

     if (l == nullptr) 
      return; 

     LN<T> *p = l; 
     LN<T> dummy(0); 
     dummy.next = l; 
     p = &dummy; 

     LN<T> *temp; 
     LN<T> *duplicate; 
     LN<T> *prev; 

     while (p != nullptr && p->next != nullptr) 
     { 
      temp = p; 
      while (p != nullptr && temp->next != nullptr) 
      { 
       if (p->value == temp->next->value) 
       { 
        duplicate = temp->next; 
        temp->next = temp->next->next; 
        delete duplicate; 

        duplicate = p; 
        prev->next = p->next; 
        p = prev; 
        delete duplicate; 

        temp = p; 
       } 
       else 
       { 
        break; 
       } 
      } 
      prev = p; 
      p = p->next; 
     } 

     l = dummy.next; 
    } 

Es scheint zu Beginn ein Bedarf an einem Dummy-Knoten zu sein, denn wenn wir 1 haben -> 1 -> 2 haben wir die ersten beiden löschen müssen, und Zeigen Sie auf den richtigen Kopf, der eine 2 ist. Um diese Verwirrung zu vermeiden, ist es besser, einen Dummy-Knoten am Anfang zu behalten und am Ende einfach die Ausgabe Ihrer Liste auf p = dummy.next zu setzen, was der tatsächliche Start ist deiner Liste.

Ich habe einige Provisorien definiert, temp und duplicate, Temp, um mir zu helfen, weiter in der Liste zu navigieren und duplizieren, um den doppelten Wert zu halten, den Zeiger zum nächsten zu bewegen und den Knoten zu löschen. prev ist der vorherige Zeiger auf den Knoten unmittelbar vor den Duplikaten.

Jeder Knoten in der Liste, temp = p Ich gehe vorwärts bis zur Suche nach der benachbarten Übereinstimmung p->value == temp->next->value Wenn es eine Übereinstimmung gibt, lösche ich den aktuellen Knoten und den, den ich vor ihm gefunden habe. Ich verwende den prev Tracker, um die Reihenfolge der Liste wiederherzustellen, indem ich next richtig setze, sonst breche ich aus meiner inneren Schleife und gehe zum nächsten Wert weiter, der äußeren Schleife p = p->next.

Ich bin mir nicht sicher über Ihre LN<T> Struktur, so dass ich mit dem fortgefahren bin, was ich denke, dass es ist.

Demo Link

Answer 2

Bevor oder nachdem Sie p löschen, sollte das Element vor p auf das Element nach den zwei gelöschten Elementen zeigen. Andernfalls wird die Linkliste unterbrochen.

Darüber hinaus können Sie für die While-Schleife nur stoppen, wenn Sie das letzte Element ankommen. Andernfalls, wenn die letzten beiden Elemente identisch sind, können Sie sie nicht korrekt löschen.

Hier ist meine Version. Ich benutzte einen Dummy-Gegenstand, um auf den Gegenstand vor dem aktuellen Vergleichsgegenstand zu zeigen. Beachten Sie, dass dies nicht 3 Artikel hintereinander behandeln kann.