如何刪除兩個項目連續在一個鏈表

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

嗨，我寫這將刪除兩個值連續在一個鏈表，如果這兩個值是相同的功能。當輸入類似於「1 - > 2 - > 3 - > 3 - > 4 - > nullptr」（輸出應該是1 - > 2 - > 4 - > nullptr）時，我的代碼似乎停止工作。它退出不會給我任何錯誤。我一行一行地進行調試，它只是突然退出並顯示「變量不可用」。

我猜這是問題，當我刪除p時，l指向垃圾，這會導致問題。所以我嘗試了一種不同的方式讓我指向to_delete - > next。但它仍然不起作用。

我已經嘗試了這麼多小時來修復它，調試甚至沒有幫助。有人可以幫忙嗎？非常感謝！

Answer 1

我簡化了上面的代碼，上面的邏輯也不會幫助您刪除多個副本。所以讓我們看看下面的代碼，並剖析它：

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; 
    } 

似乎有必要在開始虛擬節點，因爲如果我們有1 - > 1 - > 2，我們需要刪除的前兩個和指向正確的頭是2。爲了避免這種混淆，最好在開始時和結束時保留一個虛擬節點，只需將列表的輸出設置爲p = dummy.next，這是實際的開始的名單。

我定義了一些臨時對象，temp和duplicate，臨時幫助我在列表中進一步導航並複製保存重複值，將指針移到下一個並刪除節點。 prev是剛纔重複之前的節點的前一個指針。

列表中的每個節點，temp = p我向前移動，直到找到相鄰的匹配p->value == temp->next->value如果存在匹配我刪除當前節點以及我在它之前找到的節點。我使用prev跟蹤器通過正確設置其next來恢復列表的順序，否則我從內部循環中斷開並轉到下一個值，即外部循環p = p->next。

我不知道你的LN<T>結構，所以我已經走了，我認爲它是什麼。

Demo Link

Answer 2

在刪除p之前或之後，p之前的項目應指向兩個已刪除項目之後的項目。否則，鏈接列表將被破壞。

此外，對於while循環，您只能在到達最後一個項目時停下來。否則，如果最後兩個項目相同，則無法正確刪除它。

這是我的版本。我使用虛擬物品指向當前比較物品之前的物品。注意，這不能處理連續3個項目。

void delete_double (LN<T>*& l) { 
    if (l == nullptr) 
     return; 
    LN<T> *dummy = new LN<T>; 
    dummy -> next = l; 
    while (dummy -> next != nullptr && dummy -> next -> next != nullptr) // search until the last but two item 
    { 
     if (dummy -> next -> value == dummy -> next -> next -> value) // the current value is equal to the next value in the linked list 
     { 
      dummy -> next = dummy -> next -> next -> next; // link the item after dummy to the item after the deleted items   
     } 
     dummy = dummy -> next; // move dummy to the next, notice that this cannot deal with 3 items in a row 
    } 
    return; 
}