Search code examples
cstructlinked-listsingly-linked-listfunction-definition

Linked-list node eliminating function


I am just trying to eliminate nodes that are containing even numbers x % 2 == 0.

I wrote an extremely simple function but after I use it, the complier won't show the modified list and I don't get why.

If the head contains an even element it works properly (I did this in main), but when I try to delete something from the interior, it literally does not want to work...

I really don't know what I did wrong.

#include <stdio.h>
#include <stdlib.h>
struct test{
    int val;
    struct test *next;
};

void erase (struct test *x)
{ 
    struct test *t;
    t=x->next;
    x->next=t->next;
    free(t);
    return ;
}

int main ()
{
    
    struct test *head,*p,*q, *aux;
    int n,i;
    
    printf("Number of elements:");
    scanf("%d",&n);
    p=(struct test * )malloc(sizeof(struct test));
    
    printf("First value:");
    scanf("%d",&p->val);
    p->next=NULL;
    head=p;
    for(i=2;i<=n;i++)
    {
        q=(struct test * )malloc(sizeof(struct test));
        printf("Value %d:",i);
        scanf("%d",&q->val);
        q->next=NULL;
        p->next=q;
        p=q;
    }
    
    for(p=head;p!=NULL;p=p->next) {
        printf("%d ",p->val);
    }
    while((head->val)%2==0) {
        aux=head;
        head=head->next;
        free(aux);
    }
    
    for( p=head ; p!=NULL; p = p->next) {
        if((p->next->val)%2==0) {
            erase (p);
        }
    }
    printf("\n");
    for(p=head ;p!=NULL;p=p->next) {
        printf("%d ",p->val);
    }
}



Solution

  • After the while loop

    while((head->val)%2==0) {
        aux=head;
        head=head->next;
        free(aux);
    }
    

    the pointer head can be equal to NULL. So the next for loop can invoke undefined behavior. Moreover you are redundantly advancing the pointer p after erasing a node with an even value.

    Substitute this for loop

    for( p=head ; p!=NULL; p = p->next) {
        if((p->next->val)%2==0) {
            erase (p);
        }
    }
    

    for the following code

    if ( head != NULL ) {
        for( p=head ; p->next!=NULL; ) {
           if((p->next->val)%2==0) {
               erase (p);
           }
           else {
               p = p->next;
           } 
       }
    }