How to merge two sorted singly linked list

here we will discuss ,how to merge two sorted linked list such that the final list is sorted in ascending order the structure ( node ) definition is given below:

typedef struct node{
 int val;
 struct node* next;
}* node;

Explanation:
we will insert (merge ) the elements of list 2 (f2) in f1 by comparing each nodes value.

ALGORITHM:

• traverse both lists till one of them is completely traversed
• compare the values of node and if the value of node of list f1 is smaller then move to next node of f1 and increment the value of pos.
• the pos variable will be used after complete traversal to join the remaining elements of f2 if any.
• and if f2 nodes value is smaller then insert it before the current node in f1 and set f1 to previous node that is the node of f2 and increment f2 to next node.
• after completely traversing one of the lists , append the remaining elements of f2 if any in f1 .

void merge_ll(node *first){
 delete_ll(*first);*first=NULL;
 int pos=0;
 printf("Enter 1st sorted list\n");
 *first=create_ll();
 printf("Enter 2nd sorted list\n");
 node first2=create_ll();
 printf("Merging..............\n");
 node f1=*first,f2=first2;
 while(f1 && f2){
  if(f1->val < f2->val){
   f1=f1->next;
   pos++;
  }
  else{
   node prev=find_p(*first,pos);
   if(!prev){
    node temp=f2->next;
    f2->next=f1;
    *first=f2;
    f1=f2;
    f2=temp;
   }
   else{
    node t2=f2->next;
    f2->next=f1;
    prev->next=f2;
    f2=t2;
    pos++;
   }
  }
 }
 
 if(f1==NULL) find_p(*first,pos)->next=f2;

 display_ll(*first);
}

The function find_p(node first,int p) find and returns the node before the one which is at position p.
the function definition is given below:

node find_p(node first,int n){
 //index starting from 0
 node prev=NULL;
 int i;
 for(i=0;i<n&&first;i++){
  prev=first;
  first=first->next;
 }
 if(i==n && !first)return prev;//last element
 if(!first)return NULL;//not found
 return prev;//found
}

for more information on how to find nodes address at a given position : click here.

for downloading executable program for merging 2 linked list :click here




if any doubts or queries please comment