Merge Two Sorted Linked List
“Merge Two Sorted Linked List” is an intermediate problem exercise. Here, we are given two sorted linked list and our task is to merge these two sorted linked list into one sorted linked list.
For example, LIST1: 45 -> 78 -> 89 -> 93 -> 99 LIST2: 12 -> 22 -> 44 -> 66 -> 88 The merge sorted list would be: 12 -> 22 -> 44 -> 45 -> 66 -> 78 -> 88 -> 89 -> 93 -> 99
To merge two sorted linked list, there are basically two methods:
Methods 1: Join and sort
The steps required to merge two sorted linked list is as follows:
- Traverse the LIST1 to its last node.
- Now, point the pointer of last node to the head of LIST2, so as to form the single list.
- Now, sort the list using some sorting algorithm like bubble, merge or quick.
- Now, finally, we get sorted merged list.
Method 2: Sorted – Merge (inplace)
The steps required to merge two sorted linked list is as follows:
- Take two pointer ‘temp1’ and ‘temp2’ pointing to ‘list1’ and ‘list2’ respectively.
- Now traverse the lists simultaneously while one or another pointer reaches NULL.
- While traversing, we will compare the node value of both the list, if the node value of one list is smaller than node value of another, we will add the smaller node to resultant list and increment the smaller node list. If at any time both the lists node values are same, we will add both the nodes simultaneously.
- Now, we will check whether list1 or list2 completed traversed or not. If not, we will add the nodes of the remaining list to the resultant list.
C++ Program to Merge Two Sorted Linked List(METHOD 2) is as follows:
/* C++ Program to merge two sorted linked list */
#include<bits/stdc++.h>
using namespace std;
/* Structure of the node of the linked list */
typedef struct node
{
int data;
struct node *next;
}Node;
/* Function to Insert node at the end of the linked list */
void insert_end(Node **head, int ele)
{
/* Creating a new node */
Node *new_node;
new_node = (struct node*)malloc(sizeof(struct node));
new_node->data = ele;
new_node->next = NULL;
/* check whether the linked list is empty or not */
/* If Linked List is empty, then new node will become head of the linked list */
if(*head == NULL)
{
*head = new_node;
return;
}
/* If Linked List is not empty, then traverse the complete linked list and point the pointer
of last node of the linked list to the new node */
Node *temp = NULL;
temp = (*head);
while(temp->next != NULL)
temp=temp->next;
temp->next = new_node;
}
/* Function to merge two sorted linked list */
Node* SortedMerge(Node* head1, Node* head2)
{
Node *head = NULL;
Node *temp = NULL;
Node *temp1 = head1;
Node *temp2 = head2;
/*
Simultaneously, traverse both the linked list and compare data:
1. If the data of one list is smaller than other, then add smaller node to
sorted linked list and increment pointer of smaller list .
2. If the data of both the list are same, then add both of them in sorted linked
list and increment pointer of both the list.
*/
while(temp1!=NULL && temp2!=NULL)
{
if(temp1->data > temp2->data)
{
if(head == NULL)
{
head = temp2;
temp = head;
temp2 = temp2 -> next;
}
else
{
temp -> next = temp2;
temp2 = temp2 -> next;
temp = temp -> next;
}
temp -> next = NULL;
}
else if(temp1->data < temp2->data)
{
if(head == NULL)
{
head = temp1;
temp = head;
temp1 = temp1 -> next;
}
else
{
temp -> next = temp1;
temp1 = temp1 -> next;
temp = temp -> next;
}
temp -> next = NULL;
}
else
{
if(head == NULL)
{
head = temp1;
temp = head;
temp1 = temp1 -> next;
}
else
{
temp -> next = temp1;
temp1 = temp1 -> next;
temp = temp -> next;
temp -> next = temp2;
temp2 = temp2 -> next;
temp = temp -> next;
}
temp -> next = NULL;
}
}
/*
Add remaining nodes from list1 or list2, if exists
*/
while(temp1 != NULL)
{
if(head == NULL)
{
head = temp1;
temp = head;
temp1 = temp1 -> next;
}
else
{
temp -> next = temp1;
temp1 = temp1 -> next;
temp = temp -> next;
}
temp -> next = NULL;
}
while(temp2!=NULL)
{
if(head == NULL)
{
head = temp2;
temp = head;
temp2 = temp2 -> next;
}
else
{
temp -> next = temp2;
temp2 = temp2 -> next;
temp = temp -> next;
}
temp -> next = NULL;
}
return head;
}
/* Function to Print the Linked List */
void print(Node *head)
{
Node *temp = head;
while(temp!=NULL)
{
cout<<temp->data<<" ";
temp=temp->next;
}
cout<<endl;
}
int main()
{
Node *head1;
head1 = NULL;
/* Inserting Some Nodes in the first Linked List in sorted manner*/
insert_end(&head1,45);
insert_end(&head1,78);
insert_end(&head1,89);
insert_end(&head1,93);
insert_end(&head1,99);
cout<<"First Linked List:\n";
print(head1);
Node *head2;
head2 = NULL;
/* Inserting Some Nodes in the second Linked List in sorted manner*/
insert_end(&head2,12);
insert_end(&head2,22);
insert_end(&head2,44);
insert_end(&head2,66);
insert_end(&head2,88);
cout<<"\nSecond Linked List:\n";
print(head2);
Node *head = NULL;
head = SortedMerge(head1,head2);
cout<<"\nSorted Merge List:\n";
print(head);
}
OUTPUT: First Linked List: 45 78 89 93 99 Second Linked List: 12 22 44 66 88 Sorted Merge List: 12 22 44 45 66 78 88 89 93 99
Related Posts:
- Insert a New Node at the Sorted Linked List.
- Reverse a Linked List.
- Reverse a Linked List Using Stack.
- Printing Linked List in Reverse Order without actually reversing the Linked List.
- Swap Adjacent Elements of the Linked List.
- Count All Occurrences of a Particular Node in a Linked List.
- Bubble Sort on Linked List.
- Detect a Loop in a Linked List.
- Find the Length of the Loop present in the Linked List.
- Detect and Remove Loop from a Linked List.
- Segregate Even and Odd Nodes of the Linked List.
- Delete Complete Linked List.
- Delete Nth Node of the Linked List.
- Delete without head pointer of the Linked List.
- Delete All Occurrences of particular node of the Linked List.
- Delete Alternate Nodes of the Linked List.
- Delete every ‘N’ Nodes After ‘M’ Nodes of the Linked List.
- Remove Duplicate Nodes from an Unsorted Linked List.
- Remove Duplicate Nodes from a Sorted Linked List.
- Find Union and Intersection of Two Linked List.
