Monday, 13 February 2017

C Program to Merge Two Sorted Linked List (Non Recursive Approach)

In this approach, we will create a merge_sorted() function that takes two lists, each of which is sorted in increasing order, and merges the two together into one list which is in increasing order.  The new list should be made by splicing
together the nodes of the first two lists.
For example, if the first linked list a is 2->3->15 and the other linked list b is 4->9->20, then  merge_sorted() function will merge both the sorted list into a single one which will be 2->3->4->9->15->20.

Here, the merge_sorted() function is shown


This function merged both sorted Linked List into a single Linked List which is sorted in increasing order. The complete program is given below.

PROGRAM:
 

#include <stdio.h>
#include <stdlib.h>
struct node
{
    int data;
    struct node *next;
}*headA,*headB,*temp,*head;
void create_linkedList(int ch);
void print(int ch);
void merge_sorted();
int main()
{
    create_linkedList(1);
    create_linkedList(2);
    print(1);
    print(2);
    merge_sorted();
    print(3);
    return 0;
}
void create_linkedList(int ch)
{
     struct node *current;
     switch(ch)
     {
           case 1: current=(struct node*)malloc(sizeof(struct node));
                   current->data=12;
                   headA=current;
                   current->next=(struct node*)malloc(sizeof(struct node));
                   current=current->next;
                   current->data=23;
                   current->next=(struct node*)malloc(sizeof(struct node));
                   current=current->next;
                   current->data=25;
                   current->next=NULL;
                   break;
           case 2: current=(struct node*)malloc(sizeof(struct node));
                   current->data=14;
                   headB=current;
                   current->next=(struct node*)malloc(sizeof(struct node));
                   current=current->next;
                   current->data=24;
                   current->next=(struct node*)malloc(sizeof(struct node));
                   current=current->next;
                   current->data=46;
                   current->next=NULL;
                   break;
           default: printf("\nError, something went wrong");
     }
}
void merge_sorted()
{
     if(headA==NULL)
     {
            printf("\nFirst LinkedList is empty");
            head=headB;
            return;
     }
     if(headB==NULL)
     {
            printf("\nSecond LinkedList is empty");
            head=headB;
            return;
     }
     if(headA->data<=headB->data)
     {
            head=headA;
     }
     else
     {
            head=headB;
            headB=headA;
            headA=head;
     }
     while(headA->next!=NULL && headB!=NULL)
     {
            if(headA->next->data<=headB->data)
            {
                 headA=headA->next;
            }
            else
            {
                     temp=headA->next;
                     headA->next=headB;
                     headB=temp;
            }
     }
     if(headA->next==NULL)
     {
            headA->next=headB;
     }
}
void print(int ch)
{
     struct node *current;
     switch(ch)
     {
           case 1: current=headA;
                   printf("\n");
                   while(current!=NULL)
                   {
                           printf("%d->",current->data);
                           current=current->next;
                   }
                   break;
           case 2: current=headB;
                   printf("\n");
                   while(current!=NULL)
                   {
                           printf("%d->",current->data);
                           current=current->next;
                   }
                   break;
           case 3: current=head;
                   printf("\n\nThe merged Linked List is: ");
                   printf("\n");
                   while(current!=NULL)
                   {
                           printf("%d->",current->data);
                           current=current->next;
                   }
                   break;
           default: printf("\nError, something went wrong");
     }
}

OUTPUT:



In the above program, we took predetermined input, But if you want to take input from the user to create first two Linked List then you can add the code given below inside the switch statement of create_linkedList() function.


3 comments


EmoticonEmoticon