CODEWITHSUNDEEP
csortingmergelinked-listsingly-linked-list
Vegeta_sama
Vegeta_sama

Reputation: 35

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

Upvotes: 1

Views: 290

Answers (3)

chqrlie
chqrlie

Reputation: 144695

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

Upvotes: 2

wildplasser
wildplasser

Reputation: 44240

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

Upvotes: 0

Debi Prasad
Debi Prasad

Reputation: 312

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

Upvotes: 0

Related Questions