Merge two linked lists

[Hojjat.Mojallal]

Hi
I've tried the code below to merge 2 linked list which f1 and f2 are the first nodes in the initial lists and the "first" is the first node in the result list.
But it doesn't work!

node *merge(node *first,node *f1, node *f2,int n1,int n2){
    int n=n1+n2;
    while(n-- > 0){
        if(n1-- > 0)first=insert(first,f1->info);
        if(n2-- > 0)first=insert(first,f2->info);
        }
    return first;
    }

Which insert is the following function that construc a list:

node *insert(node *first, int x){
    if(first==NULL){
        first=new node;
        first->info=x;
        first->next=NULL;
        }
    else{
        node *Temp=first;
        while(Temp->next!=NULL)
            Temp=Temp->next;
        Temp->next=new node;
        Temp=Temp->next;
        Temp->info=x;
        Temp->next=NULL;
        }
    return first;
    }

Looking forward to see your advice!:)

[Narue]

One big decision you need to make in merging is whether it's destructive or not. Are you going to remove nodes from each list and add them to the result, or copy the data into new nodes?

Either way the merge works as a traversal. Select between the two lists based on some useful ordering as long as both lists are not empty. Only the selected list is moved forward. Once one list becomes empty, unconditionally copy the remaining list to the result. Consider the following:

node *merge(node *a, node *b)
{
    node *c = 0;

    while (a != 0 && b != 0) {
        if (a->info < b->info) {
            c = insert(c, a->info);
            a = a->next;
        }
        else {
            c = insert(c, b->info);
            b = b->next;
        }
    }

    while (a != 0) {
        c = insert(c, a->info);
        a = a->next;
    }

    while (b != 0) {
        c = insert(c, b->info);
        b = b->next;
    }

    return c;
}

[Hojjat.Mojallal]

Thank you dear Narue

[Hojjat.Mojallal]

I used this code and it worked:

node *merge(node *a, node *b)
{
    node *c = 0;
        while (a != 0) {
            c = insert(c, a->info);
            a = a->next;
        }
        while (b != 0) {
            c = insert(c, b->info);
            b = b->next;
        }

    return c;
}

But when I wanted to make the new list in this way:
firt(1) -> first(2) -> second(1) -> second(2) -> ...
(the numbers in parentheses referes to linked lists 1 and 2)
I modified the code in this way:

node *merge(node *a, node *b)
{
    node *c = 0;
    while(n-- > 0){        //n=n1+n2, the sum of nodes in list 1 and list 2
        if (a != 0) {
            c = insert(c, a->info);
            a = a->next;
        }
        if (b != 0) {
            c = insert(c, b->info);
            b = b->next;
        }
    }

    return c;
}

But surprisingly it doesn't work!

[Narue]

I think you'd be well served by drawing the whole process out on paper, or perhaps with a handful of change (I use the latter often when working with data structures). It'll help you visualize what needs to be done, and you'll be able to get a better feel for the steps.

[Hojjat.Mojallal]

I made the program work by changing the while condition in this way:

while(a!=0 || b!=0)

;)
Now this code does the job:

node *merge(node *a, node *b)
{
    node *c = 0;
    while(a!=0 || b!=0){
        if (a != 0) {
            c = insert(c, a->info);
            a = a->next;
        }
        if (b != 0) {
            c = insert(c, b->info);
            b = b->next;
        }
    }

    return c;
}

[mandeepsukhwinderparmar]

how to write a function that merge two sorted list L1 and L2 into L3 and L3 will contains all the items of L1 and L2