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,
- If the node in List2 is larger than List1->next then increment Lis1.
- If the node in List2 is smaller than List1->next then attach that node in List1 and increment both list.
- Some base conditions are,
- If List2 finished then return to main.
- 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 } }
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