Thread: How can I optimize this function that merges two ordered linked lists?

I am learning data structures in C and, in one exercise, I was asked to create a function that merges two ordered linked lists into a single ordered linked list. Here it is:

Code:

static struct listnode *
merge(struct listnode *a, struct listnode *b)
{
    struct listnode *head, *p;

    if (a == NULL)
        return b;
    if (b == NULL)
        return a;

    if (a->data <= b->data) {
        p = head = a;
        a = a->next;
    }
    else {
        p = head = b;
        b = b->next;
    }

    while (a != NULL && b != NULL) {
        if (a->data <= b->data) {
            p->next = a;
            a = a->next;
        } else {
            p->next = b;
            b = b->next;
        }
        p = p->next;
    }

    if (a != NULL)
        p->next = a;
    if (b != NULL)
        p->next = b;

    return head;
}

But it is full of ifs and repeated conditions, and I think my function is unnecessarily verbose. How can I optimize this function to something more short and elegant?


Here's the struct:

Code:

struct listnode {
    char data;
    struct listnode *next;
};

Code:

typedef struct listnode {
    char data;
    struct listnode *next;
} ListNode;

Code:

ListNode *merge(ListNode *a, ListNode *b)
{ 
    ListNode *head = NULL, **curr = &head;
 
    while (a && b) {
        if (a->data <= b->data) {
            *curr = a;
            a = a->next;
        } else {
            *curr = b;
            b = b->next;
        }
        curr = &(*curr)->next;
    }
 
    if (a) *curr = a;
    if (b) *curr = b;
 
    return head;
}

Or recursively (but "inefficient" since it's not tail recursion) :

Code:

ListNode *merge2(ListNode *a, ListNode *b )
{
    if (a && (!b || a->data <= b->data))
    {
        a->next = merge2(a->next, b);
        return a;
    }
    else if (b)
    {
        b->next = merge2(a, b->next);
        return b;
    }
    return NULL;
}

The recursive version is better written like this:

Code:

ListNode *merge2(ListNode *a, ListNode *b )
{
    if (!a) return b;
    if (!b) return a;
 
    if (a->data <= b->data)
    {
        a->next = merge2(a->next, b);
        return a;
    }
 
    b->next = merge2(a, b->next);
    return b;
}

No. If curr could just be a single-level pointer I would've wrote it that way since it would be simpler. The reason you need the second level of indirection is that we don't want curr to hold the value of a pointer, but instead to hold the address of where that value is stored.

By storing the address where the pointer value is stored we can write to that address by dereferencing curr, modifying the value (which itself happens to be a pointer) at that address. It is this ability that allows us to eliminate some of the repetitive code in your attempt. The way you did it, there is a fundamental difference between "head" and all of the "next" pointers, and you need separate code to deal with that difference. But by using another level of indirection and pointing to the place where the pointers are stored, the "head" storage location and the "next" storage locations all look the same and can be handled by the same piece of code.

This is similar to john.c's answer, but only checks for a == NULL or b == NULL as needed, instead of a while that checks both for every node moved.

Code:

ListNode * MergeLists(ListNode *a, ListNode *b)
{
ListNode *head;
ListNode **curr = &head;
    if(a == NULL)                       /* if either list empty, */
        return b;                       /*  return the other */
    if(b == NULL)
        return a;
    while(1){                           /* merge the lists */
        if(a->data <= b->data){
            *curr = a;
            curr = &(a->next);
            a = *curr;
            if(a == NULL){
                *curr = b;
                break;}}
        else{
            *curr = b;
            curr = &(b->next);
            b = *curr;
            if(b == NULL){
                *curr = a;
                break;}}}
    return head;
}