Program to merge two sorted linked lists

Given two sorted linked list which are sorted in increasing order. Write a function to merge these two sorted linked list.
 Here is simple C program to merge linked list using recursion.

C Program:

#include<stdio.h>
#include<stdlib.h>
 
struct Node 
{
 int data;
 struct Node *next;
};
 
struct Node *CreateNode(int n)
{
struct Node *newNode=(struct Node*)malloc(sizeof(struct Node));
       newNode->data = n;
       newNode->next = NULL;
       return newNode;
}
 
/* Function to insert node at the beginning of 
linked list. */
struct Node *Insert(struct Node *head,int n)
{
 struct Node *newNode = CreateNode(n);
 
 if(head==NULL)
 {
  head = newNode;
 }
 else
 {
  newNode->next = head;
  head = newNode;
 }
 
 return head;
}
 
void PrintList(struct Node *head)
{
 struct Node *curr = head;
 if(curr==NULL)
 {
  printf("List is empty");
 }
 else
 {
 while(curr!=NULL)
 {
  printf("%d ",curr->data);
  curr = curr->next;
 }
 
 }
 printf("\n");
}
 
struct Node *SortedMerge(struct Node *AHead,struct Node *BHead)
{
 struct Node *result;
 /* If first list is empty */
 if(AHead==NULL)
 return BHead;
 else
 /* If second list is empty */
 if(BHead==NULL)
 return AHead;
 else
 if(AHead->data<=BHead->data)
 {
  result = AHead;
  result->next = SortedMerge(AHead->next,BHead);
 }
 else
 {
  result = BHead;
  result->next = SortedMerge(AHead,BHead->next);
 }
 
 return result;
}
 
int main()
{
 struct Node *AHead = NULL;
 struct Node *BHead = NULL;
 /* We are inserting node in sorted manner. Our
 task is to merge two sorted linked list */
 AHead = Insert(AHead,65);
 AHead = Insert(AHead,63);
 AHead = Insert(AHead,61);
 AHead = Insert(AHead,59);
 BHead = Insert(BHead,67);
 BHead = Insert(BHead,63);
 BHead = Insert(BHead,54);
 BHead = Insert(BHead,23);
 PrintList(AHead);
 PrintList(BHead);
 
 struct Node *newHead;
 newHead = SortedMerge(AHead,BHead);
 PrintList(newHead);
 
 return 0;
}



Popular posts from this blog