Merge 2 sorted linked list in reverse order[Microsoft Interview Question]

Problem:Given two linked lists sorted in increasing order. Merge them both in such a way that the result list is in decreasing order. Both the Linked list can be of different sizes.

/*

The structure of linked list is the following

struct Node
{
int data;
Node* next;
};

*/

struct Node * mergeResult(Node *node1,Node *node2)
{
    // your code goes here
    Node *head,*tmp,*tmp2;
    Node *p;
    bool f=0;
    int a,b;
    tmp=node1;
    tmp2=node2;

    while(tmp!=NULL && tmp2!=NULL)
    {
        a=tmp->data;
        b=tmp2->data;
        if(a<b)
        {
            tmp=tmp->next;
            if(f==0)
            {
                head=new Node;
                head->data=a;
                head->next=NULL;
                f=1;
            }
            else
            {
                p=new Node;
                p->data=a;
                p->next=head;
                head=p;
            }

        }
        else if(a>b)
        {
            tmp2=tmp2->next;
            if(f==0)
            {
                head=new Node;
                head->data=b;
                head->next=NULL;
                f=1;
            }
            else
            {
                p=new Node;
                p->data=b;
                p->next=head;
                head=p;
            }
        }
        else if(a==b)
        {
            tmp=tmp->next;
            tmp2=tmp2->next;
            if(f==0)
            {
                head=new Node;
                head->data=b;
                p=new Node;
                p->data=b;
                p->next=NULL;
                head->next=p;
                f=1;
            }
            else
            {
                p=new Node;
                p->data=a;
                p->next=head;
                head=p;

                p=new Node;
                p->data=b;
                p->next=head;
                head=p;
            }
        }
    }

    while(tmp!=NULL)
    {
        a=tmp->data;
        p=new Node;
        p->data=a;
        p->next=head;
        head=p;
        tmp=tmp->next;
    }

    while(tmp2!=NULL)
    {
        a=tmp2->data;
        p=new Node;
        p->data=a;
        p->next=head;
        head=p;
        tmp2=tmp2->next;
    }

    return head;
}

 

Leave a Reply

Your email address will not be published. Required fields are marked *