如何从单链表中删除每第 10 个节点？

Question

我正在为即将到来的测试编写学习指南，我们需要准备好为链表实现一个奇怪的函数，以确保我们真正理解它们。

我们应该创建一个方法：void decimate();删除每 10 个节点。但是，当我在调用 decimate() 后打印列表时，列表保持不变。我错过了什么？

    void decimate()
    {

        //iterate through the list
        //keep a counter
        //when counter is 10, remove that node

        temp = head;
        for(int i = 0; i < 10; i++)
        {
            temp = temp->next;
        }
        prev = temp;
        prev->next = temp->next;
        delete temp;


    }

Answer 1

这两行中的第二行什么都不做：

prev = temp; prev->next = temp->next;

如果您将 prev 设置为 temp 那么 prev.next 已经是 temp.next 不是吗？

编辑。所以我被要求提供一个伪答案，我想这很公平......你需要考虑跳过被删除的节点，你需要指向被删除的项目指向的内容而不是指向的内容保留对您删除的那个的引用。

Answer 2

您必须像下面这样修改您的方法。您必须始终有一个指针指向要删除的节点，即此处的 team。请看我下面的评论。它们非常重要。

 void decimate()
{

    //iterate through the list
    //keep a counter
    //when counter is 10, remove that node

    temp = head;
    for(int i = 0; i < 10; i++)
    {
        prev = temp;// this line of code should be here
        //prev is pointing to team and in below code temp is pointing to the next node
        temp = temp->next;
    }
            // here `prev->temp;` prev is pointing to temp
            prev->next = temp->next;// now prev is point to the node next to temp;
            //after the above code temp is detached from the list
            delete temp;
}

现在看看你的错误：-

 prev = temp;// prev and temp both are pointing to the same node
 prev->next = temp->next;// wrong nothing going to happen
 delete temp; 
// if you make temp = NULL; here you will lost the rest of the list

同样删除其实不破坏内存区。它将保持不变。删除只是将该区域标记为仅供 re-allocation/re-use 免费。这就是为什么即使删除后您仍然可以看到整个列表的原因。

Answer 3

您正在尝试将 prev 分配给 temp，而不是将 prev 分配给 temp 的前一个，然后删除 temp。并且您的 decimate() 函数正在删除唯一的第 10 个元素，而不是每第 10 个元素，因此请检查这是否符合预期。

如何从单链表中删除每第 10 个节点？

How to delete every 10th node from singly linked list?

c++

pointers

linked-list

singly-linked-list