Write a c program to merge two sorted linked lists in sorted order.  For example if one linked list is 1->2->3->null and other is 1->3->5->6->null then the output should be 1->1->2->3->3->5->6->null.

## How to approach solution

• Take two pointers head and current.
• head pointer will point to first node only.
• To solve this problem we need to traverse both the linked list.
• During traversal check the node value of linked list. Suppose if the one linked list is l1 and another is l2.
• if the node value of l1 is less than equal to the node value of l2, then append l1 to current.
• else append l2 to current.

## C Program to merge two sorted linked lists

```#include <stdio.h>
#include <malloc.h>

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

list *l1 = NULL;
list *l2 = NULL;

list* create_node(int val);

list* merge(list* l1, list* l2)
{
if (l1 == NULL) return l2;
if (l2 == NULL) return l1;
list *p1 = l1;
list *p2 = l2;
list *cur = NULL;

while (p1 && p2)
{
{
if (p1->val <= p2->val)
{
p1 = p1->next;
}
else
{
p2 = p2->next;
}
}
else
{
if (p1->val <= p2->val)
{
cur->next = p1;
cur = p1;
p1 = p1->next;
}
else
{
cur->next = p2;
cur = p2;
p2 = p2->next;
}
}
}
if (p1) cur->next = p1;
if (p2) cur->next = p2;

}

int main()
{
l1 = create_node(1);
l1->next = create_node(2);
l1->next->next = create_node(3);
l1->next->next->next = NULL;

// create  1->3->5->6->null
l2 = create_node(1);
l2->next = create_node(3);
l2->next->next = create_node(5);
l2->next->next->next = create_node(6);
l2->next->next->next->next = NULL;

list *res = merge(l1, l2);
print(res);
return 0;
}

list* create_node(int val)
{
list *tmp = (list*) malloc(sizeof(list));
tmp->next = NULL;
tmp->val = val;
return tmp;
}
{
while (current)
{
printf("%d ", current->val);
current = current->next;
}
printf("\n");
}

```

## Recursive approach

• We have two linked lists l1 and l2 in sorted order.
• The  size of l1 could be equal to the size of l2.
• The size of l1 could be greater than the size of l2.
• The size of l1 could be less than the size of l2.
• So the recursive call of merge(l1->next,l2) or merge(l1,l2->next) , would return when smaller list ends. in this case merge the rest of the another list.

#### Let us see the code ( recursive function to merge two sorted linked lists)

```list* merge(list* l1, list* l2)
{
// if l1 is empty
if (l1 == NULL) return l2;
// if l2 is empty
if (l2 == NULL) return l1;

if (l1->val <= l2->val)
{
l1->next = merge(l1->next, l2);
return l1;
}
else
{
l2->next = merge(l1,l2->next);
return l2;
}
}
```

Request:

Send some article to myarticle@wikistack.com to help others.