c++ - 删除链接列表中的每隔三个节点

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

看看你的 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 函数，我不想假设太多。但至少，它应该具有删除节点的功能——如果没有，则它缺少任何链表实现应具有的基本功能。