# 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:
2 -- > 4 --> 6 --> 9 --> NULL
1 --> 4 --> 5 --> 8 --> NULL
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

• 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.

## 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  */
printf("Inserted Element : %d\n", num);
}

struct node* mergeLinkedList(struct node* LLOne, struct node* LLTwo){
while(1){
/* */
if(LLOne == NULL){
resultTail->next = LLTwo;
break;
}

if(LLTwo == NULL) {
resultTail->next = LLOne;
break;
}

/* Check whether current node of
if(LLOne->data <= LLTwo->data){
temp = LLOne;
LLOne = LLOne->next;
} else {
temp = LLTwo;
LLTwo = LLTwo->next;
}
} else {
resultTail->next = temp;
resultTail = temp;
}
resultTail->next = NULL;
}

}

/*
*/
while (nodePtr != NULL) {
printf("%d", nodePtr->data);
nodePtr = nodePtr->next;
if(nodePtr != NULL)
printf("-->");
}
}

int main() {
initialize();
insert(&LLOne, 9);
insert(&LLOne, 6);
insert(&LLOne, 3);
insert(&LLOne, 1);
printf("\n");
insert(&LLTwo, 10);
insert(&LLTwo, 6);
insert(&LLTwo, 5);
insert(&LLTwo, 2);

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