删除链表中的每三个节点

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以前可以工作。但是在我使用了三重函数后，它停止了工作。我做错了什么？

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

Answer 2

可以通过以下方式定义函数

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.