delete all duplicated nodes in unsorted linked list-CodePudding

the main purpose of my code is that to take a data from the user and then search the single linked list to find the target and then delete all the nodes that are equal to target. this is also the base single linked list:

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

Input: 1, 2, 3, 2, 5 --> to delete= 2

so the new linked list is: 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;

}

this is my to-delete function I wrote. it works for the target items that are in the middle of the linked list but when the firstNode which is head of the list is the target it either doesn't deletes it or looses the head address and i tried to do many ways to save the head of the list so that it wont loose it.

it also doesn't work for the situation that the last node it the target.

I was struggling with this problem but i couldn't solve it so i would be happy and thankful if someone helps me with this.

CodePudding user response：

For starters the function returns nothing though its return type is void *.

This while loop

while ( NULL != current->next)

can invoke undefined behavior if the function is called for an empty list.

Also the while loop is skipped when the list contains only one node.

Or for example if the first node contains a value that is equal to the parameter target then in the first iteration of the loop the pointed node will be freed. However in the next iteration of the loop you are again checking the deleted node

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

}

that one more invokes undefined behavior.

The function can be declared and defined the following way

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

And if in the caller of the function you have

no *firstNode;

then the function is called like

toDElduplicatedlinkedlist( &firstNode, target );

That is the pointer to the first node of the list is passed by reference.

Another way to define the function is the following

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;
}

In this case the function is called like

firstNode = toDElduplicatedlinkedlist( firstNode, target );

And at last the function can be also defined the following way

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;
}

and called the same way as shown above that is

firstNode = toDElduplicatedlinkedlist( firstNode, target );

CodePudding user response：

One needs a pointer to a pointer to modify the head node given the function, and one should merely loop while current is not null.

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

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

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

}