c - 从C中指针指向的列表中删除数据

Question

我已经尝试了一段时间来找出一种递归方法来删除节点(从链接列表中的任何位置)而不留下任何内存泄漏。

这可能吗？

这是我的非递归方法，不起作用:

    int removeItem(struct ListNode** headRef, int data)
    {
    struct ListNode* temp = *headRef; // store original head
    int val = data;
    while (temp->next != NULL)
    {
    if (temp->next->data != val)
    {
    temp = temp->next;
    }
    else if (temp->next->data == val)
    {
    temp = temp->next;
    free(temp);
    return 1;
  }
  else
  {
  return 0;
   }
 }
 return 0;
 }

Answer 1

老实说，我不确定我是否遵循了这个问题，但这就是您想要做的吗？

int removeItem(struct ListNode** headRef, int data)
{
    if (!*headRef)
        return 0;

    if ((*headRef)->data != data)
        return removeItem(&(*headRef)->next, data);

    // found it. drop it out.
    struct ListNode *tmp = *headRef;
    *headRef = tmp->next;
    free(tmp);
    return 1;
}

如果是的话，不要。最好通过迭代来完成此任务(您可能会发现它有点难以理解，但如果您了解递归解决方案，我无法想象为什么):

int removeItem(struct ListNode** headRef, int data)
{
    while (*headRef && (*headRef)->data != data)
        headRef = &(*headRef)->next;

    if (*headRef)
    {
        struct ListNode *tmp = *headRef;
        *headRef = tmp->next;
        free(tmp);
        return 1;
    }
    return 0;
}

它们如何工作

这两个函数的工作原理都是使用 headRef 来始终保存引用我们正在测试的节点的指针地址。

最初，headRef 包含列表的 head 指针的地址。每次我们需要移动到下一个节点时，我们都会在 headRef 中加载引用该节点的指针地址。当我们最终找到我们要寻找的节点时，引用它的指针的地址就在 headRef 中(可能是原来的 head 指针，也可能是某个 next 指向列表中某处的指针；哪一个并不重要)。

这两个函数之间的区别很简单。首先，我们使用递归将要测试的下一个指针的地址传递给递归调用。在第二个中，我们只使用迭代循环。无论哪种方式，headRef 始终保存指向我们正在测试的节点的指针的地址。如果我们找到赢家(在本例中为输家)，请注意两个函数执行相同的操作:将值保存在*headRef中(它的指针正在释放)，用当前节点的 next 的值填充 *headRef，然后删除旧节点。把它画在纸上会有很大帮助(我的 ASCII 艺术很糟糕；抱歉)。