I'm trying to merge two sorted linked lists but I'm not getting any output, I'm trying to traverse through the two linked list while comparing the data and adding the smaller element to my final linked list. I'm using pushback() to add the element at the end:

void merge_sort(struct node *a, struct node *b)
{
    struct node *ans = (struct node *)malloc(sizeof(struct node));
    ans = NULL;
    while (a != NULL || b != NULL)
    {
        if ((a->data >= b->data) || (a == NULL && b != NULL))
        {
            pushback(&ans, b->data);
            b = b->next;
            // display(ans);
        }
        if ((b->data > a->data) || (b == NULL && a != NULL))
        {
            pushback(&ans, a->data);
            a = a->next;
            // display(ans);
        }
    }
    display(ans);
}

CodePudding user response：

Your approach has multiple problems:

• you do not merge the lists, but attempt to construct a third list with the values from the 2 lists.

• you allocate an initial node to ans, but you immediately set ans = NULL; thereby losing the reference to the allocated memory, causing a memory leak.

• it is unclear what push_back does as it is not a standard function and you do not provide source code nor a specification.

• testing (a->data >= b->data) has undefined behavior if either a or b is a null pointer. You should test for the validity of the pointers before accessing the data members.

• merge_sort should return the new list ans.

Here is a modified version:

struct node *merge_sort(const struct node *a, const struct node *b)
{
    struct node *ans = NULL;
    while (a != NULL || b != NULL) {
        if (a != NULL && (b == NULL || a->data <= b->data)) {
            pushback(&ans, a->data);
            a = a->next;
        } else {
            pushback(&ans, b->data);
            b = b->next;
        }
    }
    //display(ans);
    return ans;
}

If you are supposed to merge the lists without allocating any memory, here is an alternative:

struct node *merge_sort(struct node *a, struct node *b)
{
    struct node *ans;
    struct node **link = &ans;

    while (a != NULL && b != NULL) {
        if (a->data <= b->data) {
            *link = a;
            link = &a->next;
            a = a->next;
        } else {
            *link = b;
            link = &b->next;
            b = b->next;
        }
    }
    *link = (a != NULL) ? a : b;
    //display(ans);
    return ans;
}

CodePudding user response：

void merge_sort(struct node *a, struct node *b)
{
    struct node *ans = (struct node *)malloc(sizeof(struct node));
    ans = NULL;
    while (a != NULL && b != NULL)
    {
        
        if ((a->data >= b->data))
        {
            pushback(&ans, b->data);
            b = b->next;
            // display(ans);
        }
        else if ((b->data > a->data))
        {
            pushback(&ans, a->data);
            a = a->next;
            // display(ans);
        }
        
    }
    while(a != NULL)
    {
       pushback(&ans,a->data);
       a=a->next;
    }
    while(b != NULL)
    {
       pushback(&ans,b->data);
       b=b->next;
    }
    display(ans);
}

In your solution, you will miss out on the cases when the length of linked lists is not the same, and also the cases where the elements of a particular linked list get over. try this one, it will work out well if you have defined the display() and the pushback() functions correctly.
You must also mention the exact order in which the linked list are sorted(in that case, you might have to reverse the linked lists before applying this algorithm)

it would be better if you provide the whole code which includes the definition of all the functions along with the output snippet, so that we can have idea of what might be the exact problem

CodePudding user response：

Standard solution, using a pointer-to-pointer:

struct node * merge_sort(struct node *one, struct node *two)
{
    struct node *ans , **pp;

    ans = NULL;
    for(pp = &ans; one && two; pp = &(*pp)->next) {
        
        if (one->data <= two->data) {
            *pp = one;
            one = one->next;
        }
        else    {
            *pp = two;
            two = two->next;
            }
        
    }
        /* At this point, either one or two is exhausted.
        ** or both: in that case NULL will be assigned to *pp
        */
    *pp = (one) ? one : two;

    return ans;
}