# Merge Two Sorted List | Microsoft | Samsung

### Question

Write a program to merge two sorted list. Given two linked lists of size N which is sorted in ascending order and print the merged list. This Program is asked in Amazon, Microsoft, Flipkart, Makemytrip, Samsung, etc.

Note: It is strongly recommended to do merging in-place using O(1) extra space.

### Logic

• Initially find the list with smallest head node and use that as List1(L1).
•  There are some conditions,
1. If the node in List2 is larger than  List1->next then increment Lis1.
2. If the node in List2 is smaller than List1->next then attach that node in List1 and increment both list.
• Some base conditions are,
2. If the node in List2 is larger than the current node in List1 then attach List2 at the end of List1.
• Print the sorted list.

### Program

```#include<stdio.h>
struct node{
struct node* next;
int data;
};
struct node* createNode(int data)
{
struct node* temp = NULL;
temp = (struct node*)malloc(sizeof(struct node));
temp->data = data;
temp->next=NULL;
return temp;

}
void traverse(struct node* root)
{
if(root!=NULL)
{
printf("%d\n",root->data);
traverse(root->next);
}
}
/*we use double pointer so all the changes in list will be reflected in main function*/
void MergeList(struct node** list1, struct node** list2)
{
struct node* temp;
temp=(struct node*)malloc(sizeof(struct node));
struct node* L1 = *list1;
struct node* L2= *list2;

while(L1 !=NULL || L2!= NULL)
{
if(L2==NULL)
break;                  //break if list2 finished

if(L1->next == NULL) {
/*if node in list2 is larger then connect list2 to list1*/
if(L2->data > L1->data)
{
L1->next = L2;
break;
}
}

/*if next node in list1 is smaller*/
if(L1->next->data < L2->data )
{
L1 = L1->next;             //increment node pointer
continue;
}

else if(L1->next->data > L2->data)
{
/*attach L2 node in L1*/
temp = L1->next;            //store in temporary node
L1->next = L2;              //connect list2 node with list1
L2 = L2->next;
L1 = L1->next;
L1->next = temp;            //connect temporary node

continue;
}
}
}

int main()
{
struct node *list1,*list2;
list1 = (struct node*)malloc(sizeof(struct node));
list2 = (struct node*)malloc(sizeof(struct node));
/*Creating two sorted list*/
list1 = createNode(2);
list1->next = createNode(4);
list1->next->next = createNode(20);
list2 = createNode(1);
list2->next = createNode(15);
list2->next->next = createNode(35);

traverse(list1);
traverse(list2);

struct node* merge;
merge = (struct node*)malloc(sizeof(struct node));
/*Finding list with smallest head node*/
if(list1->data < list2->data)
{
MergeList(&list1,&list2);
traverse(list1);               //new merged list
}
else
{
MergeList(&list2,&list1);
traverse(list2);              //new merged list
}

}
```

#### 3.Insert a node at a specific position in LinkedList ### Sree Hari Sanjeev

The founder and CEO of Wisdom Overflow. His enthusiasm and effort has taken the blog to next level. You will be motivated just by taking a look at his daily schedule.