C语言 删除链表中的节点

35g0bw71  于 2023-10-16  发布在  其他
关注(0)|答案(2)|浏览(102)

给定链表的头和一个整数val,删除链表中所有具有Node.val == val的节点,并返回新的头。
这是我的尝试

struct ListNode *removeElements(struct ListNode *head, int val) {
    struct ListNode *tmp, *prev;

    if (head == NULL)
        return head;

    for (tmp = head, prev = NULL; tmp != NULL; prev = tmp, tmp = tmp->next)
        if (tmp->val == val) {
            prev->next = tmp->next;
            free(tmp);
        }

    return head;
}

但我发现了分割错误问题看起来很简单,但我不知道我错在哪里。

57hvy0tb

57hvy0tb1#

如果第一个节点的值为val,则语句prev->next = tmp->next;将导致分段错误,因为prev是空指针。在你的方法中,你必须对列表的开头做一个特殊的处理:

struct ListNode *removeElements(struct ListNode *head, int val) {
    while (head != NULL && head->val == val) {
        struct ListNode *tmp = head;
        head = head->next;
        free(tmp);
    }
    if (head != NULL) {
        for (struct ListNode *prev = head, *cur = head->next; cur != NULL;) {
            if (cur->val == val) {
                struct ListNode *tmp = cur;
                prev->next = cur = cur->next;
                free(tmp);
            } else {
                prev = cur;
                cur = cur->next;
            }
        }
    }
    return head;
}

下面是一个使用双指针的简单解决方案:

struct ListNode *removeElements(struct ListNode *head, int val) {
    struct ListNode **pp = &head;
    struct ListNode *tmp;
    while ((tmp = *pp) != NULL) {
        if (tmp->val == val) {
            *pp = tmp->next;
            free(tmp);
        } else {
            pp = &tmp->next;
        }
    }
    return head;
}
qojgxg4l

qojgxg4l2#

这个for循环

for (tmp = head, prev = NULL; tmp != NULL; prev = tmp, tmp = tmp->next)
    if (tmp->val == val) {
        prev->next = tmp->next;
        free(tmp);
    }

有三个问题
主要问题是循环本身并不改变指针(变量)head
因此,如果头节点的数据成员val等于变量val的值,则指针head的值将不会改变。
第二个问题是,最初指针prev等于NULL。因此,如果指针head指向的节点将被删除,则在此语句中使用空指针来访问内存

prev->next = tmp->next;

这会导致未定义的行为。
最后第三个问题是,可以使用已经删除的节点

free(tmp);

在for循环的表达式中

tmp = tmp->next

同样在这种情况下,指针prev被设置为指向被删除节点的指针tmp

prev = tmp

可以实施两种方法。
第一个是首先检查指针head所指向的节点。
给你.

struct ListNode * removeElements( struct ListNode *head, int val ) 
{
    if ( head != NULL )
    {
        while ( head->val == val )
        {
            struct ListNode *tmp = head;
            head = head->next;
            free( tmp );
        }

        if ( head != NULL )
        {
            for ( ListNode *current = head; current->next != NULL; )
            {
                if ( current->next->val == val )
                {
                    ListNode *tmp = current->next;
                    current->next = current->next->next;
                    free( tmp );
                }
                else
                {
                    current = current->next;
                }
            }
        }
    }

    return head;
}

第二种方法是通过指向列表中的指针来引用它们。

struct ListNode * removeElements( struct ListNode *head, int val ) 
{
    for ( struct ListNode **current = &head; *current != NULL; )
    {
        if ( ( *current )->val == val )
        {
            struct ListNode *tmp = *current;
            *current = ( *current )->next;
            free( tmp );
        }
        else
        {
            current = &( *current )->next;
        }
    }

    return head;
}

请注意,你应该始终在使用变量的最小范围内声明变量。

相关问题