CODEWITHSUNDEEP
clinked-liststructured-data
G. Bittencourt
G. Bittencourt

Reputation: 155

Split linked list in C

I need to implement some divide-and-conquer algorithms (binary search, merge sort, etc) using linked lists.
To do this, I need to define a method that divides a certain list into two, so that the size difference between them is a maximum of 1 element.
That's my structure:

typedef struct linked_list *L;
typedef struct linked_list{
    int info;
    L next;
};

L is a pointer to a linked_list.

The code below is my algorithm attempt that splits the given list into front and back halves.
I couldn't think of a way to return two generated lists, so I pass two empty lists as parameters.

void split_list(L r, L front, L back){
    L a = r->next;
    L b = r;

    while( a ){
        a = a->next; 
        if ( a->next ){
            a = a->next;
            b = b->next;
        }
    }

    back = b->next;
    front = r;
    b->next = NULL;

}

However, when you run the function on the main, it does not work as expected.

L z = NULL;
/ insert some nodes in z /

L x = NULL;
L y = NULL;

split_list(z, x, y);

Trying to print x and y, they are empty (apparently).
I believe the problem is in the way that the lists are passed as a parameter, but I don't know exactly how to solve this.

Upvotes: 1

Views: 105

Answers (1)

4386427
4386427

Reputation: 44339

You have a classic C misunderstanding.

You are trying to change x in main by passing x to a function and then change the corresponding variable in the function. You can't do that!

Simplified example of approach that does not work:

void foo(int x)
{
    x = 55;
}

int globalInt = 42;

void bar(int* p)
{
    p = &globalInt;
}

void main(void)
{
    int x = 0;
    foo(x);
    printf("%d\n", x);  // Will print 0

    int* p = NULL;
    bar(p);
    printf("%p\n", (void*)p); // Will print NULL (nil)

    return 0;
}

The reason is that C pass variables by value (not by reference). So when you pass x to the function, you really pass the value 0 and the function has know idea that the value 0 comes from a variable named x.

So in your case both x and y in main will still be NULL after the function call.

To change the variables in main you need to pass the address of the variables.

void foo(int* x)  // Notice the extra *
{
    *x = 55;      // Notice the extra *
}

int globalInt = 42;

void bar(int** p)      // Notice the extra *
{
    *p = &globalInt;   // Notice the extra *
}

void main(void)
{
    int x = 0;
    foo(&x);            // Notice the & operator
    printf("%d\n", x);  // Will print 55

    int* p = NULL;
    bar(&p);                  // Notice the & operator
    printf("%p\n", (void*)p); // Will print address of the global variable

    return 0;
}

General rule

If you see C code like:

TYPE x = SomeValue;
func(x);

you know for sure that x will also have the value SomeValue after the function call.

About your code

So in your case you need:

void split_list(L r, L* front, L* back)

However, since you assign front to r it seems overkill to change it in the function and you could simply do:

L split_list(L r) {...}

and call it like:

L back = split_list(head);
// Now head contains first half and back contains second half

BTW:

It's opinion based but typedef of pointers are in general not a good idea.

Upvotes: 1

Related Questions