Merge Two Sorted Linked List

Suppose you are given two linked lists which are both sorted into ascending order, then you have to merge these two separate sorted (ascending) linked lists into one sorted linked list.

For example if you have,

Linked List 1 = 3, 4, 5

Linked List 2 = 7, 8, 9

then, you should write a merge function for the above two linked list such that it will merge and return a single linked list as shown below,

Merged Linked list = 3, 4, 5, 7, 8, 9

Steps to merge two sorted linked list :

• First create two separate sorted(ascending) linked lists.

• Initialise two pointers p and q of type struct node to point the first node of each created sorted linked list.

Now write a merge function.

• If p is NULL, then return q i.e., return list2 and if q is NULL, then return p i.e., return list1.

• Initialise a dummy pointer sort of type struct node to merge two linked list and also initialise another pointer head3 to point the first node of resultant merged linked list.

• If both the list exists, then check is p->data <= q->data. If yes, then dummy pointer sort will point to p and p is updated to p->next else sort will point q and q is updated to q->next.

• Make pointer head3 to point to the node to which dummy pointer sort is pointing. This head3 pointing node will be the first node of the resultant merged linked list .

Note : At this point, pointer sort will be pointing to the node which contains the smallest data among the two list. Pointers p or q will be pointing to the immediate next node of the node pointing to by sort.

• Check p->data <= q->data. If yes, then create a link between a node pointing to by sort and a node pointing to by p and then update both the pointers by one node ahead else create a link between a node pointing to by sort and a node pointing to by q and then update both the pointers by one node ahead. Repeat this process until one of the linked list becomes NULL.

• If p becomes NULL first then create a link between sort and q.
  If q becomes NULL first then create a link between sort and p.

• Return head3.

• Display the merged sorted linked list.
  

#include<stdio.h>
#include<stdlib.h>

struct node
{
    int data;
    struct node * next;
};
struct node * merge(struct node * p , struct node * q , struct node * sort)
{
    struct node *  head3;

    if(p == NULL)
        return q;

    if(q == NULL)
        return p;

    if(p && q)
    {
        if(p->data <= q->data)
        {
            sort = p;
            p = sort->next;
        }
        else
        {
            sort = q;
            q = sort->next;
        }

    }

    head3 = sort;

    while(p && q)
    {
        if(p->data <= q->data)
        {
            sort->next = p;
            sort = p;
            p = sort->next;
        }
        else
        {
            sort->next = q;
            sort = q;
            q = sort->next;
        }
    }

    if(p==NULL)
    {
        sort->next = q;
    }

    if(q==NULL)
    {
        sort->next = p;
    }

    return head3;   
}

int main()
{
    struct node * p=NULL , * q=NULL , * head1=NULL , * head2=NULL , * sort = NULL;
    int n1 , n2 , a;

    printf("Enter the number of nodes in the first Linked List: ");
    scanf("%d",&n1);

    printf("Enter the number of nodes in the second Linked List: ");
    scanf("%d",&n2);

    if(n1 > 0)
    {
    printf("Enter the data1 of first Linked List: ");
    scanf("%d",&a);
    p = (struct node* )malloc(sizeof(struct node));
    p->data = a;
    p->next = NULL;
    head1 = p;
    }

    for(int i=1; i<n1; i++)
    {
        printf("Enter the data%d: ", i+1);
        scanf("%d",&a);
        q = (struct node* )malloc(sizeof(struct node));
        q->data = a;
        q->next = NULL;
        p->next = q;
        p = p->next;        
    }

    if(n2 > 0)
    {
    printf("Enter the data1 of second Linked List: ");
    scanf("%d",&a);
    p = (struct node* )malloc(sizeof(struct node));
    p->data = a;
    p->next = NULL;
    head2 = p;
    }

    for(int i=1;i<n2;i++)
    {
        printf("Enter the data%d: ", i+1);
        scanf("%d",&a);
        q = (struct node* )malloc(sizeof(struct node));
        q->data = a;
        q->next = NULL;
        p->next = q;
        p = p->next;        
    }
    p = head1;
    q = head2;
    printf("\n First Linked List : ");
    while(p!=NULL)
    {
        printf("%d  ",p->data);
        p = p->next;
    }

    printf("\n Second Linked List: ");
    while(q!=NULL)
    {
        printf("%d  ",q->data);
        q = q->next;
    }

    p = head1;
    q = head2;
    sort = merge(p  , q , sort);

    printf("\n");
    printf("\n Sorted Merged Linked List: ");
    while(sort!=NULL)
    {
        printf("%d  ",sort->data);
        sort = sort->next;
    }
    return 0;
}

For more detail watch this video.

I own a website www.coderlogs.com where in I write similar blogs so do visit the website for more such blog posts.