Splitting list into two separate positive and negative lists

Question

I wrote a function splitting one linked list into two, where passed list keeps positive numbers and returns negative numbers list.

struct elem {
    int val;
    struct elem *next;
};

struct elem *create(int val) {
    struct elem *temp;

    temp=(struct elem*) malloc(sizeof(struct elem));
    temp->val = val;
    temp->next = NULL;
    return temp;
}

void addToEnd(struct elem* list, int nval) {
    struct elem *temp = list;
    struct elem *new_list = create(nval);
    if(temp == NULL) {
        list = new_list;
        return;
    }
    while(temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = new_list;
}


struct elem* split(struct elem** list) {
    struct elem* prev;
    struct elem* temp = *list;

    struct elem* positive = (struct elem*) malloc(sizeof(struct elem));
    struct elem* negative = (struct elem*) malloc(sizeof(struct elem));

    while(temp != NULL) {
        if(temp->val > 0) addToEnd(positive, temp->val);
        else if(temp->val < 0) addToEnd(negative, temp->val);
        prev = temp;
        temp = temp->next;
        free(prev);
    }

    *list = positive;
    return negative;
}

After using this function both of my lists contain 0 as a first value, no matter what values the passed list contains before using function. How to fix this?

Answer 1

The function addToEnd accepts the pointer to the head node in the list by value.

void addToEnd(struct elem* list, int nval) {
              ^^^^^^^^^^^^^^^^^   

That is the function deals with a copy of the value of the pointer to the head node.

So assigning to the copy of the argument a new value in this if statement

if(temp == NULL) {
    list = new_list;
    return;
}

does not change the original pointer to the head node.

You need to pass the pointer to the head node by reference through a pointer to it.

Within the function split allocating memory like for example in these declarations

struct elem* positive = (struct elem*) malloc(sizeof(struct elem));
struct elem* negative = (struct elem*) malloc(sizeof(struct elem));

or in these statements

    if(temp->val > 0) addToEnd(positive, temp->val);
    else if(temp->val < 0) addToEnd(negative, temp->val)

does not make sense because nodes were already allocated. What you need is to move nodes with negative values in a new list.

Here is a demonstrative program that shows how it can be done.

#include <stdio.h>
#include <stdlib.h>

struct elem 
{
    int val;
    struct elem *next;
};

struct elem * create( int val ) 
{
    struct elem *temp = malloc( sizeof( *temp ) );
    
    if ( temp != NULL )
    {
        temp->val  = val;
        temp->next = NULL;
    }
    
    return temp;
}

int addToEnd( struct elem **list, int val ) 
{
    struct elem *temp = create( val );
    int success = temp != NULL;
    
    if ( success )
    {
        while ( *list ) list = &( *list )->next;
        
        *list = temp;
    }

    return success;
}

struct elem*  split( struct elem **list )
{
    struct elem *new_list = NULL;
    struct elem **current = &new_list;
    
    while ( *list )
    {
        if ( ( *list )->val < 0 )
        {
            *current = *list;
            *list = ( *list )->next;
            ( *current )->next = NULL;
            current = &( *current )->next;
        }
        else
        {
            list = &( *list )->next;
        }
    }
    
    return new_list;
}

void display( const struct elem *list )
{
    for ( ; list != NULL; list = list->next )
    {
        printf( "%d -> ", list->val );
    }
    puts( "null" );
}

int main(void) 
{
    struct elem *list = NULL;
    
    const int N = 10;
    
    for ( int i = 0; i < N; i++ )
    {
        addToEnd( &list, i % 2 != 0 ? -i : i );
    }
    
    display( list );
    
    struct elem *new_list = split( &list );
    
    display( list );
    display( new_list );
    
    return 0;
}

The program output is

0 -> -1 -> 2 -> -3 -> 4 -> -5 -> 6 -> -7 -> 8 -> -9 -> null
0 -> 2 -> 4 -> 6 -> 8 -> null
-1 -> -3 -> -5 -> -7 -> -9 -> null