Search code examples
csortingmergelinked-listsingly-linked-list

im trying to merge two sorted linked list in ascending order but im not getting the correct output


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);
}

Solution

  • 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