刪除每三個節點在鏈表

Question

我有刪除的鏈接列表每三個節點的功能：

void tricimate() 
    { 
    node * toDelete = head->next->next; 
    while (toDelete != NULL) 
    { 
     if (toDelete->next == NULL) 
     { 
      tail = tail->prev; 
      tail->next = NULL; 
      delete toDelete; 
      break; 
     } 
     node * ahead = toDelete->prev; 
     node * behind = toDelete->next; 
     ahead->next = behind; 
     behind->prev = ahead; 
     delete toDelete; 
     toDelete = behind->next->next; 
    } 

} 

它的工作原理，但是當我嘗試使用的47值添加節點，它不不添加它。我有這樣的：

29 7 2 3 31 37 

當我應該有這樣的：

29 7 2 3 31 37 47 

這是我添加新節點到鏈表的後部代碼：

void addBack(int x) 
{ 
    node * newItem = new node; 
    if (head == NULL && tail == NULL) 
    { 
     newItem->data = x; 
     newItem->next = NULL; 
     newItem->prev = NULL; 
     head = newItem; 
     tail = newItem; 
    } 
    else 
    { 
     newItem->data = x; 
     newItem->next = NULL; 
     newItem->prev = tail; 
     tail->next = newItem; 
     tail = newItem; 
    } 
} 

我不不明白什麼是錯誤的，因爲addBack以前工作。但是在我使用tricimate函數後，它停止工作。我究竟做錯了什麼？

Answer 1

的功能可以被定義如下方式

void tricimate() 
{ 
    node *current = head; 

    while (current && (current = current->next) && (current = current->next)) 
    { 
     node *toDelete = current; 

     current->prev->next = current->next; 
     if (current->next != nullptr) 
     { 
      current->next->prev = current->prev; 
     } 
     else 
     { 
      tail = current->prev; 
     } 

     current = current->next; 

     delete toDelete; 
    } 
} 

至於你的函數，那麼對於初學者甚至它的第一條語句就是錯

void tricimate() 
    { 
    node * toDelete = head->next->next; 
    //.... 

因爲一般head或head->next可以等於nullptr。

Answer 2

看着你的tricimate函數，它看起來像是一個過度的東西，導致了「過度編碼」。

要刪除每第三個節點（假設鏈接列表至少有3個節點），代碼可以將計數器設置爲1，在循環中遞增計數器，並且如果計數器可以平均除以3，則刪除節點。

你應該做的是寫一個函數，從列表中刪除任何節點（稱爲remove_node）。如果有，則函數刪除所有的第三結點就變得簡單了：

void tricimate() 
{ 
    int counter = 1; 
    node* curNode = head; 
    while (curNode) 
    { 
     node *nextNode = curNode->next; // save for the next iteration 
     if (counter % 3 == 0) // if we're on the node we want to delete... 
     remove_node(curNode); // remove it. 
     ++counter;    // increment count 
     curNode = nextNode;  // go to next node. 
    } 
} 

請注意，我並沒有實現remove_node功能。我不知道你的鏈表的其餘部分是如何實現的，所以如果我試圖編寫remove_node函數，我不想過多地假設它。但至少它應該有一個刪除節點的功能 - 如果沒有，它缺少任何鏈表實現應該具有的基本功能。