从单链表的中间删除一个节点？

Question

我知道这个问题已经被问过很多次了，但我似乎仍然无法弄清楚我遇到的错误。这是我的代码：

int remove(ListNode * &head, int length)
{
    if(head != NULL)
    {
        string str = head->word;
        if(str.size() > length)
        {
            if(head->next->next != NULL)
            {
                head->word = head->next->word;
                ListNode* tempNode = head->next->next;
                delete head->next; //segfault
                head->next = tempNode;
                return 1 + remove(head->next, length);
            }
            else if(head->next != NULL)
            {
                head->word = head->next->word;
                delete head->next;
                head->next = NULL;
                return 1 + remove(head->next, length);
            }
            else
            {
                delete head;
                head = NULL;
                return 1 + remove(head->next, length); 
            }
        }
        else
        {
            return remove(head->next, length);
        }
     }

     return count;
}

目标是删除任何大小大于参数中给定长度的单词。当我尝试删除 head->next 时发生错误，即使它显然存在并且我也能够打印出这个词。我得到的错误是

* Error in `./a.out': double free or corruption (out): 0x00007ffde3d4d7c0 * Aborted (core dumped)

我尝试在其上运行 Valgrind，但无法解释输出，因为它没有指定任何行号。感谢您对这个简单问题的任何帮助。

Answer 1

Note: The first part of this answer was before OP edited the code (see new answer below)

这部分：

head == NULL;
return remove(head->next, length, count + 1);
              ^^^^

不好。

首先，你不应该设置：

head == NULL; 
     ^^

应该是：

HEAD = NULL;

此外，之后您不应该再次调用该函数：

return remove(head->next, length, count + 1);

完成后（您刚刚删除了 head 元素，因此 head 为 NULL）。只需 return 0;（或您想要 return 的任何值）。

Answer to edited question

你的新代码的一个问题是这个结构：

        if(head->next->next != NULL)  // Here you know that head isn't NULL
        {                             // but head->next can still be NULL so
            ....                      // don't do head->next->next !
        }
        else if(head->next != NULL)   // This check should also be part
        {                             // of your first if-statement. Like:
            ....                      // if ((head->next != NULL) && (head->next->next != NULL))
        }
        else
        {
            ....
        }

总的来说，我不认为使用递归函数调用对这个问题有好处。非递归方法是：

int remove(ListNode * &head, int length)
{
    if(head == NULL)
    {
        // empty
        return 0;
    }

    ListNode *tmp;
    int removed = 0;

    // Remove elements from start of list
    while(true)
    {
        string str = head->word;
        if(str.size() > length)
        {
            // Remove head element
            tmp = head;
            head = head->next;
            delete tmp;
            ++removed;
            if (head == NULL)
            {
                return removed;
            }
        }
        else
        {
            // No more head elements to remove
            break;
        }
    }

    // Remove elements from middel to end
    tmp = head;
    while(tmp->next)
    {
        string str = tmp->next->word;
        if(str.size() > length)
        {
            // Remove element tmp->next
            ListNode *tmp2 = tmp->next;
            tmp->next = tmp->next->next;
            delete tmp2;
            ++removed;
        }
        else
        {
            // Keep current tmp->next and move to next element
            tmp = tmp->next;
        }
    }

    return removed;
}

从单链表的中间删除一个节点？

Removing a node from the middle of a singly-linked list?

c++

linked-list

singly-linked-list