删除未排序链表中的所有重复节点

Question

我的代码的主要目的是从用户那里取一个数据，然后搜索单链表找到目标，然后删除所有等于目标的节点。这也是基础单链表：

typedef struct Node
{
    int data;
    struct Node *next;
}no;

输入： 1, 2, 3, 2, 5 --> 删除= 2

所以新的链表是：1,3,5

void* toDElduplicatedlinkedlist (no* firstNode, int target)
{

    no* current = firstNode;
    no* ptemp;

while ( NULL != current->next)
{


    if (firstNode->data == target)
    {
        current = firstNode->next;
        free(firstNode);

    }

    else if (current->next->data == target)
        {
            ptemp = current->next;
            current->next= current->next->next;
            free(ptemp);
        }

        current = current->next;

}

这是我写的删除功能。它适用于位于链表中间的目标项，但是当列表头部的 firstNode 是目标时，它不会删除它或丢失头部地址，我尝试做很多保存列表头部以使其不会丢失的方法。

也不适用于最后一个节点为目标的情况。

我一直在努力解决这个问题，但我无法解决它，所以如果有人能帮助我，我会很高兴和感激。

Answer 1

对于初学者来说，函数 return 什么都不是，尽管它的 return 类型是 void *。

这个while循环

while ( NULL != current->next)

如果为空列表调用该函数，则可以调用未定义的行为。

当列表只包含一个节点时，也会跳过 while 循环。

或者例如，如果第一个节点包含一个等于参数目标的值，那么在循环的第一次迭代中，指向的节点将被释放。但是，在循环的下一次迭代中，您将再次检查已删除的节点

if (firstNode->data == target)
{
    current = firstNode->next;
    free(firstNode);

}

再调用一个未定义的行为。

函数可以通过以下方式声明和定义

void toDElduplicatedlinkedlist( no **firstNode, int target )
{
    while ( *firstNode )
    {
        if ( ( *firstNode )->data == target )
        {
            no *tmp = *firstNode;
            *firstNode = ( *firstNode )->next;
            free( tmp );
        }
        else
        {
            firstNode = &( *firstNode )->next;
        }
    }
}

如果在函数的调用者中你有

no *firstNode;

那么函数就这样调用

toDElduplicatedlinkedlist( &firstNode, target );

即指向列表第一个节点的指针通过引用传递。

另一种定义函数的方法如下

no * toDElduplicatedlinkedlist( no *firstNode, int target )
{
    while ( firstNode && firstNode->data == target )
    {
        no *tmp = firstNode;
        firstNode = firstNode->next;
        free( tmp );
    }

    if ( firstNode != NULL )
    {
        for ( no *current = firstNode; current->next != NULL; )
        {
            if ( current->next->data == target )
            {
                no *tmp = current->next;
                current->next = current->next->next;
                free( tmp );
            }
            else
            {
                current = current->next;
            }
        }
    }
      
    return firstNode;
}

在这种情况下函数被调用为

firstNode = toDElduplicatedlinkedlist( firstNode, target );

最后函数也可以这样定义

no * toDElduplicatedlinkedlist( no *firstNode, int target )
{
    for ( no **current = &firstNode; *current; )
    {
        if ( ( *current )->data == target )
        {
            no *tmp = *current;
            *current = ( *current )->next;
            free( tmp );
        }
        else
        {
            current = &( *current )->next;
        }
    }

    return firstNode;
}

调用方式同上，即

firstNode = toDElduplicatedlinkedlist( firstNode, target );

Answer 2

需要一个指向指针的指针来修改给定函数的头节点，并且应该只在当前不为空时循环。

void* toDEduplicatedlinkedlist(no** firstNode, int target)
{

    no* current = *firstNode;
    no* ptemp = *firstNode;

    while (NULL != current)
    {
        no* temp = NULL;
        if (current->data == target)
        {
            if (current == *firstNode) {
                *firstNode = current->next;
            }
            else {
                ptemp->next = current->next;
            }
            temp = current;
        }
        else {
            ptemp = current;
        }
        current = current->next;
        if(temp != NULL) free(temp); 
    }
    return *firstNode;
}

删除未排序链表中的所有重复节点

delete all duplicated nodes in unsorted linked list

c

struct

free

singly-linked-list

function-definition