删除单向链表中所有出现的元素

Question

我花了几个小时编写了一个函数 - 给定一个 linked 列表单向列表，将删除给定元素的所有出现。这是我设法编写的函数：

void remove_by_value(struct Node **head, int value) {
    while( *head!=NULL && (*head)->value == value ) {
        struct Node *tmp = *head;
        if((*head)->next != NULL)
            *head = (*head)->next;
        else
            *head = NULL;
        free(tmp);
    }

    struct Node *iterator = *head;
    while(iterator->next != NULL) {
        if(iterator->next->value == value) {
            struct Node *tmp = iterator;
            iterator = iterator->next;
            free(tmp);
            continue;
        }
        iterator = iterator->next;
    }
}

在我的示例中，我使用的是一个简单的列表，如下所示：2->1->1 以及我在运行 remove_by_value(&head, 1) 之后的程序输出：

0 
1242177584 
Segmentation fault (core dumped)

与预期效果相去甚远。问题是我不明白我的错误在哪里。这是我想要应用的算法：

检查此列表的头部是否具有所需的值。如果是这样，将头部向右移动并删除第一个节点。重复直到新头的值与这个函数的参数不同
检查下一个节点的值是否等于期望值。如果是，则删除该节点和link当前节点以及被删除节点之后的节点。

我知道我的算法并不完美——例如，当节点没有指向任何东西时，它无法处理这种情况。但问题的核心是我不明白为什么我的程序会这样。你能给我一些建议吗？有没有更好的方法来编写这个算法？

编辑：
我认为这可能很重要，所以我决定包括我的打印功能，因为它可能会根据我以前的功能导致一些潜在的内存泄漏：

void print(struct Node *head) {
    while(head != NULL) {
        printf("%d \n", head->value);
        head = head->next;
    }
}

Answer 1

我认为这应该可行，但太复杂而无法验证。如果没有，将删除 post。

void remove_by_value(struct Node **head, int value) {
    while( *head!=NULL && (*head)->value == value ) {
        struct Node *tmp = *head;
        *head = (*head)->next;     /*removed some useless code here*/
        free(tmp);
    }
    struct Node *iterator = *head;
    if(iterator == NULL)
        return;
    while(iterator->next != NULL) {
        if(iterator->next->value == value) {
            struct Node *tmp = iterator->next;
            iterator->next = iterator->next->next; 
            free(tmp);
        }
        iterator = iterator->next;
    }
}

解释（感谢下面的评论）：

原代码测试iterator->next是否应该删除，但错误地删除了iterator it self。例如2->1->1，2会被删除，因为下一个节点是1，其实应该删除的是1

删除链表中的元素时，释放应删除的节点是不够的。还需要将前一个节点的"next"变量设置为删除元素后的节点

例如2->1->3 OP 的代码：2->Null Nothing->3；正确：2->3

P.S。我的答案有问题，但是好像不能删除我接受的答案。

下面更好的答案： https://whosebug.com/users/2877241/vlad-from-moscow

你的函数太复杂并且有一个错误，因为在第二个 while 循环中没有检查 head 是否等于 NULL 并且循环更改局部变量迭代器而不是更改节点本身。

功能可以更简单的实现。例如

void remove_by_value( struct Node **head, int value ) 
{
    while ( *head )
    {
        if ( ( *head )->value == value )
        {
            struct Node *tmp = *head;
            *head = ( *head )->next;
            free( tmp );
        }
        else
        {
            head = &( *head )->next;
        }
    }
}

这是一个演示程序

#include <stdio.h>
#include <stdlib.h>

struct Node
{
    int value;
    struct Node *next;
};

void insert(struct Node **head, const int a[], size_t n)
{
    for (size_t i = 0; i < n; i++)
    {
        struct Node *current = ( struct Node * )malloc(sizeof(struct Node));

        current->value = a[i];
        current->next = *head;

        *head = current;
        head = &(*head)->next;
    }
}

void print( struct Node *head ) 
{
    for ( ; head != NULL; head = head->next )
    {
        printf( "%d ", head->value );
    }
}

void remove_by_value( struct Node **head, int value ) 
{
    while ( *head )
    {
        if ( ( *head )->value == value )
        {
            struct Node *tmp = *head;
            *head = ( *head )->next;
            free( tmp );
        }
        else
        {
            head = &( *head )->next;
        }
    }
}

int main(void) 
{
    struct Node *head = NULL;
    int a[] = { 2, 1, 1 };

    insert( &head, a, sizeof( a ) / sizeof( *a ) );

    print( head );
    putchar( '\n' );

    remove_by_value( &head, 1 );

    print( head );
    putchar( '\n' );

    remove_by_value( &head, 2 );

    print( head );
    putchar( '\n' );

    return 0;
}

它的输出是

2 1 1 
2

Answer 2

所以你的删除函数的第一个循环是可以的，但是有点笨拙。这段代码非常多余，因为无论值 next 是什么，您都将其分配给 *head

if((*head)->next != NULL)
    *head = (*head)->next;
else
    *head = NULL;

但它所做的只是在第一个节点与您要查找的值匹配时删除它，这并不是特别有用。

这是下一个循环的问题，因为它没有正确更新您的列表。假设您的列表是 1 -> 2 -> 3 而您要删除 2。您遍历列表直到到达中间节点。您获取当前节点的临时副本，将自己指向下一个节点，然后释放它。哪个让你的列表像 1 -> 2？？？ 3 因为你还没有更新前一个节点指向下一个节点。

你可以只用一个循环来完成所有的事情。您使用 head 作为跟踪指向当前节点的任何内容的一种方式。所以在循环的开始它指向列表的开始。如果该节点不匹配，则将其指向当前节点的下一个指向的任何位置。

如果匹配，您将再次获取当前节点的临时副本，但这次您更新 *head 以指向下一个节点。所以它将保持先前的连接或列表的开始。

void remove_by_value(struct Node **head, int value) {
    while( *head!=NULL ) {
        if ((*head)->value == value) {
            struct Node *tmp=*head;
            *head=(*head)->next;
            free(tmp);
        } else {
            head=&((*head)->next);
        }
    }
}

Answer 3

你的函数太复杂并且有一个错误，因为在第二个 while 循环中没有检查 head 是否等于 NULL 并且循环更改局部变量 iterator 而不是更改节点他们自己。

功能可以更简单的实现。例如

void remove_by_value( struct Node **head, int value ) 
{
    while ( *head )
    {
        if ( ( *head )->value == value )
        {
            struct Node *tmp = *head;
            *head = ( *head )->next;
            free( tmp );
        }
        else
        {
            head = &( *head )->next;
        }
    }
}

这是一个演示程序

#include <stdio.h>
#include <stdlib.h>

struct Node
{
    int value;
    struct Node *next;
};

void insert(struct Node **head, const int a[], size_t n)
{
    for (size_t i = 0; i < n; i++)
    {
        struct Node *current = ( struct Node * )malloc(sizeof(struct Node));

        current->value = a[i];
        current->next = *head;

        *head = current;
        head = &(*head)->next;
    }
}

void print( struct Node *head ) 
{
    for ( ; head != NULL; head = head->next )
    {
        printf( "%d ", head->value );
    }
}

void remove_by_value( struct Node **head, int value ) 
{
    while ( *head )
    {
        if ( ( *head )->value == value )
        {
            struct Node *tmp = *head;
            *head = ( *head )->next;
            free( tmp );
        }
        else
        {
            head = &( *head )->next;
        }
    }
}

int main(void) 
{
    struct Node *head = NULL;
    int a[] = { 2, 1, 1 };

    insert( &head, a, sizeof( a ) / sizeof( *a ) );

    print( head );
    putchar( '\n' );

    remove_by_value( &head, 1 );

    print( head );
    putchar( '\n' );

    remove_by_value( &head, 2 );

    print( head );
    putchar( '\n' );

    return 0;
}

它的输出是

2 1 1 
2

Answer 4

曾经有一段时间，程序员不得不经常做这类事情，当你做的足够多之后，你的代码就会变得非常高效。为了帮助保持这种古老艺术的活力，下面是这样一个函数的样子：

void removeByValue(Node **head, int val){
    Node *n;
    while(n=*head) {
        if (n->value == val) {
            *head = n->next;
            free(n);
        } else {
            head = &(n->next);
        }
    }
}

删除单向链表中所有出现的元素

Remove all occurences of an element in a one-way linked list

c

linked-list

list

data-structures

singly-linked-list