无法从链表中删除最后一个元素

Question

我无法从链表中删除最后一个元素，问题是当我删除它时，我拥有的唯一节点是前一个节点（在最后一个节点之前）。这是我的代码：

node *remove_node(int d, node *lst){
    node *prev;
    node *temp = lst;
    if(temp->data == d){
        if(temp->next != NULL){
            node *sec_temp = temp;
            temp = temp->next;
            free(sec_temp);
            return temp;
        }
        else{
            free(temp);
            return NULL;
        }
    }
    while(temp != NULL && temp->data != d){
        prev = temp;
        temp = temp->next;
    }
    if(temp == NULL){return lst;}
    //Here is the problem
    if(temp->next == NULL){
        prev->next = NULL;
        free(temp);
        return prev;
    }
    //end
    else {
        prev->next = temp->next;
        free(temp);
        return prev;
    }
}
int main(){
    node *lst = NULL;
    lst = new_node(1, lst);
    lst = new_node(2, lst);
    lst = new_node(3, lst);
    lst = new_node(4, lst);
    lst = remove_node(1, lst);
    print(lst);// this will print the list, works perfect
    return 0;
}

当我删除 1（这是列表中的最后一个元素）时，只会打印 2，在所有其他情况下一切正常（如果我删除 2 或 3 或 4 我没有任何问题。 ). 有什么想法可能会导致问题吗？

Answer 1

你把事情搞得比需要的复杂得多。有几种方法可以删除正向 linked、空终止 linked 列表中的节点。您可以使用两个指针（前一个指针和当前指针）来完成它，这似乎是您正在尝试的。在理解实际算法之前停止编码：

node *remove_node(int d, node *lst)
{
    node *prev = NULL, *cur = lst;

    while (cur && cur->data != d)
    {
        prev = cur; 
        cur = cur->next;
    }

    if (cur)
    {
        if (!prev) // head node was the match
            lst = lst->next;
        else
            prev->next = cur->next;
        free(cur);
    }
    return lst;
}

工作原理

最初我们有两个指针，prev 指向列表中的前一个节点到当前测试节点并且最初为 NULL，cur，我们正在测试的当前节点，最初是列表头。

一次遍历列表一个节点，每次测试我们是否 (a) 尚未到达列表末尾 (cur != NULL) 和 (b) 找到与我们的目标数据匹配的节点(cur->data == d)。我们相应地打破循环。一旦循环中断，cur 要么指向要删除的节点，要么为 NULL，这意味着我们找不到匹配项。

prev 的值仅在 cur 为非 NULL 时才重要，这意味着我们找到了匹配项。如果我们找到一个匹配项并且 prev == NULL 我们必须在头节点上，否则 prev 指的是 next 指针需要 link 到 cur->next 指针来拼接列表并在删除之前删除我们的受害者。

仅此而已。我强烈建议您通过调试器手动执行删除操作，并查看指针沿途处理的内容。调试器不仅仅用于查找损坏的东西。它们是帮助更好地理解代码工作原理的绝佳工具（因为您实际上 "see" 它在工作）。

祝你好运。

Answer 2

问题是你 returns 指向被删除元素之前的元素的 prev 指针，但实际上列表的开头仍然是 lst 指针。接下来在 main 方法中，您在打印方法中使用返回的指针，因此您只打印最后一个元素。

无法从链表中删除最后一个元素

cannot remove the last element from linked list

c

linked-list