c - 使用递归删除链表中所有出现的数字

Question

我想编写一个程序，使用递归从一个简单的链表中删除所有出现的数字，所以我尝试了但我遇到了问题:我编写的程序删除了列表中的所有出现但它没有删除存在于开头的那个(存在于第一个节点的出现)，这里是C中的代码:

typedef struct list {
    int data;
    struct list *next;
} list;

list *delete(int x, list *head) {
    if (head->next == NULL)
        return head;
    list *newnode = delete(x, head->next);
    if (newnode->data == x) {
        head->next = head->next->next;
        free(newnode);
    }
    return head;
}

我希望有人能帮助我改进我的算法，在此先感谢。

Answer 1

代码中存在多个问题:

• 您取消引用 head 而不先检查它是否为 NULL。该函数无法处理空列表。
• 如果列表只有一个元素，您可以在不测试其值的情况下显式返回 head 节点。
• 在 head->next 上递归后，您只测试列表的第二个元素。因此，第一个元素永远不会被测试。

这是一个修改后的版本，它只测试第一个节点并递归列表的其余部分:

list *delete(int x, list *head) {
    if (head == NULL)
        return head;
    if (head->data == x) {
        list *node = head;
        head = head->next;
        free(node);
        return delete(x, head);
    }
    head->next = delete(x, head->next);
    return head;
}