- 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,Singly linked list's node structure is as follows:Merged Linked List1 --> 2 --> 4 --> 4 --> 5 --> 6 --> 8 --> 9 --> NULL

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