Merge Two Sorted Linked List

• Write a C program to merge two sorted linked list into one linked list.

Given two linked list sorted in increasing order. We have to merge sorted linked lists and return a new single linked list which contains nodes of both linked list in increasing order.

For Example:
First sorted Linked List
2 -- > 4 --> 6 --> 9 --> NULL
Second sorted Linked List
1 --> 4 --> 5 --> 8 --> NULL
Then, Merged Linked List
1 --> 2 --> 4 --> 4 --> 5 --> 6 --> 8 --> 9 --> NULL 

Singly linked list's node structure is as follows:

struct node {
    int data;
    struct node *next;
}

Here, we will write a function "struct node* mergeLinkedList(struct node* LLOne, struct node* LLTwo)" which takes head pointer of two sorted linked list and return head pointer of merged linked list.

---

Algorithm to merge two sorted linked list

Let LLOne and LLTwo be the head pointer of two sorted linked list and resultHead and resultTail are the head and tail pointer of merged linked list.

• Initilaize resultHead and resultTail to NULL. resultHead = resultTail = NULL;
• If first linked list is empty, then attach whole of second list at the tail of merged linked list. if(LLOne == NULL) then resultTail->next = LLTwo;
• If second linked list is empty, then attach whole of first list at the tail of merged linked list. if(LLTwo == NULL) then resultTail->next = LLOne;
• Check which of the current nodes of both linked list is smaller and then remove it from linked list.
• Add the smalled node at the tail of merged linked list.
• Repeat above process, until one of the linked list or both becomes empty.
• Return head pointer of merged linked list. return resultHead.

---

C program to merge two sorted linked list

include <stdio.h>
#include <stdlib.h>
 
/* A structure of linked list node */
struct node {
  int data;
  struct node *next;
} *LLOne, *LLTwo, *mergedLL;

void initialize(){
    LLOne = LLTwo = mergedLL = NULL;
}
/* 
Given a Inserts a node in front of a singly linked list. 
*/
void insert(struct node **head, int num) {
    /* Create a new Linked List node */
    struct node* newNode = (struct node*) malloc(sizeof(struct node));
    newNode->data  = num;
    /* Next pointer of new node will point to head node of linked list  */
    newNode->next = *head;
    /* make new node as new head of linked list */
    *head = newNode;
    printf("Inserted Element : %d\n", num);
}

struct node* mergeLinkedList(struct node* LLOne, struct node* LLTwo){
    struct node *resultHead, *resultTail, *temp;
    resultHead = resultTail = NULL;
    while(1){
        /* */ 
        if(LLOne == NULL){
            resultTail->next = LLTwo;
            break;
        }
        
        if(LLTwo == NULL) {
            resultTail->next = LLOne;
            break;
        }
        
        /* Check whether current node of 
        which Linked list is smaller*/
        if(LLOne->data <= LLTwo->data){
            temp = LLOne;
            LLOne = LLOne->next;
        } else {
            temp = LLTwo;
            LLTwo = LLTwo->next;
        }
        /*Add smaller node to result linked list  */
        if(resultHead == NULL){
            resultHead = resultTail = temp;
        } else {
            resultTail->next = temp;
            resultTail = temp;
        }
        resultTail->next = NULL;
    }
    
    return resultHead;
}

/*
Prints a linked list from head node till tail node 
*/
void printLinkedList(struct node *nodePtr) {
  while (nodePtr != NULL) {
     printf("%d", nodePtr->data);
     nodePtr = nodePtr->next;
     if(nodePtr != NULL)
         printf("-->");
  }
}
 
int main() {
    initialize();
    /* Creating First linked List*/
    insert(&LLOne, 9);  
    insert(&LLOne, 6); 
    insert(&LLOne, 3); 
    insert(&LLOne, 1);
    printLinkedList(LLOne);
    printf("\n");
    /* Creating Second linked List*/
    insert(&LLTwo, 10);  
    insert(&LLTwo, 6); 
    insert(&LLTwo, 5); 
    insert(&LLTwo, 2);
    printLinkedList(LLTwo);
    /* Merge Linked List */
    mergedLL = mergeLinkedList(LLOne, LLTwo); 
    printf("\nMerged Linked List\n");
    printLinkedList(mergedLL);
    
    return 0;
}

Output

Inserted Element : 9
Inserted Element : 6
Inserted Element : 3
Inserted Element : 1
1-->3-->6-->9
Inserted Element : 10
Inserted Element : 6
Inserted Element : 5
Inserted Element : 2
2-->5-->6-->10
Merged Linked List
1-->2-->3-->5-->6-->6-->9-->10