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,

1. If List2 finished then return to main.
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

[code lang=”c”]
#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
}

}
[/code]

Suggested Reading…

1.Program to add two numbers represented as List

2.Merge two sorted array without duplicates

3.Insert a node at a specific position in LinkedList