Merging two sorted linked lists !!


The problem is just like merging step in merge sort, wherein we have two sorted arrays and merge them into one. If you haven’t already gone through the linked list concepts, I would recommend you to go through that first. The algorithm is simple and stated as:


struct node *merge(struct node *p,struct node *q)
{
        struct node *r,*s;
        struct node *a=NULL;
        r=p; s=q;
        while(r !=NULL && s!= NULL)
        {
                if(r->data <= s->data)
                {
                        a=insert(a,r->data);
                        r=r->link;
                }
                else{
                        a=insert(a,s->data);
                        s=s->link;
                }
        }
        if(r==NULL)
                while(s!=NULL)
                {
                        a=insert(a,s->data);
                        s=s->link;
                }
        else
                while(r!=NULL)
                {
                        a=insert(a,r->data);
                        r=r->link;
                }
        return a;
}

About these ads
  1. #1 by Alexwebmaster on March 3, 2009 - 11:05 am

    Hello webmaster
    I would like to share with you a link to your site
    write me here preonrelt@mail.ru

  2. #2 by vie90 on June 20, 2009 - 2:46 pm

    thanks for all

  3. #3 by Kashif on January 27, 2011 - 6:38 pm

    // merges two Singly linked lists A and B, both sorted in increasing order of integers .
    // Return a Singly linked list sorted in increasing order
    // for ex if A = 1->2->3->6 and B = 2->4->7, returns 1->2->2->3->4->6->7

    public LinkedList merge(LinkedList A, LinkedList B) {

    Node 1A = A.head;
    Node 1B = B.head;
    Node P1A = NULL;
    Node 2A = NULL;
    Node 2B = NULL;

    while ( 1A != NULL && 1B !=NULL){
    2A = 1A.next;
    2B = 1B.next;

    if (1A.item >= 1B.item) {
    if (P1A != NULL) {
    P1A.next = 1B;
    }
    else if ( P1A == NULL){
    P1A = 1B;
    }
    1B.next = 1A;
    P1A = 1B;
    1B = 2B;
    }
    else if ( 1A.item < 1B.item){
    if ( 2A != NULL) {
    P1A = 1A;
    1A = 1A.next;
    }
    else{
    1A.next = 1B;
    break;
    }
    }
    }
    return A;
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: