Home > Back-end >  Recursive function to create a linked list with certain elements of another linked list in c
Recursive function to create a linked list with certain elements of another linked list in c

Time:10-25

i have this recursive function:

struct singly* SetMinusRec(struct singly* shead1, struct singly* shead2){
    struct singly* s2end;

    s2end = shead2;

    if(shead1 == NULL){
        return NULL;
    }else{
        while(s2end != NULL && shead1->id < s2end->id){
            s2end = s2end->next;
        }
        
        struct singly* new = (struct singly*)malloc(sizeof(struct singly));

        if(shead1->id == s2end->id){
            /* How can i not add this to the list, but just move on to the next node? */
        }

        printf("-%d %d-\n", shead1->id, s2end->id);

        new->id = shead1->id;
        new->next = SetMinusRec(shead1->next, shead2);    
        return new;
    }
}

Basically, shead2 is sorted with decreasing order, and shead1 with increasing, and i want to create a new list, which has the elements of shead1 that dont exist in shead2. What am i supposed to do when they have the same id? How can i move on to the next node?

Thanks a lot.

CodePudding user response:

This memory allocation

struct singly* new = (struct singly*)malloc(sizeof(struct singly));

can produce a memory leak if shead1->id == s2end->id.

On the other hand, if memory will not be allocated due to the equation and the pointer new will be set to NULL then this statement

new->next = SetMinusRec(shead1->next, shead2);

will invoke undefined behavior.

Also this if statement

if(shead1->id == s2end->id){

and this test output

printf("-%d %d-\n", shead1->id, s2end->id);

again can invoke undefined behavior if after the while loop the pointer s2end is equal to NULL.

The function can be declared and defined the following way

struct singly * SetMinusRec( const struct singly *shead1, const struct singly *shead2 )
{
    struct singly *shead = NULL;

    if ( shead1 != NULL )
    {
        const struct singly *current = shead2;

        while ( current != NULL && shead1->id < current->id )
        {
            current = current->next;
        }

        if ( current == NULL || current->id < shead1->id )
        {
            shead = malloc( sizeof( struct singly ) );

            shead->id   = shead1->id;
            shead->next = SetMinusRec( shead1->next, shead2 );
        }
        else
        {
            shead = SetMinusRec( shead1->next, shead2 );
        }
    }

    return shead;
}
  • Related