Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
In this article, we will learn how to Merge two sorted linked list such that the final linked list is also sorted in linear time O(N).
Table of contents:
- Problem Statement: Merge two sorted linked lists
- Algorithm
- Implementation (Step by Step)
Let us get started with Merge two sorted linked lists.
Problem Statement: Merge two sorted linked lists
Merge two given sorted linked list and return head of new linked list which should also be sorted.
Example :
Input: linked list 1 = {1,2,4} , linked list 2 = {1,3,4}
Output: {1,1,2,3,4,4}
Time Complexity :
O(n), beacuse of only one loop iterating only one time.
Algorithm
The steps to Merge two sorted linked lists are:
- Traverse both Linked Lists linearly from the first node
- Compare current nodes of both Linked List
- Delete the smaller node
- Insert the smaller node at the end of final Linked List
- If one Linked List is empty during processing, move all elements of the other sorted Linked List to the end of the final Linked List
- The final Linked List is the merged Linked List.
The implementation steps are:
1.First we define a node by either using struct or class.
2.Create a function to create new nodes.
3.Create a function which takes two sorted linked lists as input and return head of merged linkedlist.
4.Create a function to display the linked list and write main function.
Implementation (Step by Step)
Step 1 : Defining a node
We can do this by either using struct or class.
struct node{
int data;
struct node* next;
};
or
class node{
public:
int data;
node* next;
};
Step 2 : Function to create a new node
node* newnode(int key)
{
struct node* temp = new node;
temp->data = key;
temp->next = NULL;
return temp;
}
Step 3 : Function to merge sorted linked lists
Approach :
-
Check if linked list 1 is empty return linked list 2 , or if linked list 2 is empty return linked list 1.
-
Create new head of the merged linked list by comparing both linked list first elements and choosing the smaller value beacuse we want to maintain the order (should be sorted).
-
Now, for rest of the elements compare them one by one in a while loop and maintain a new pointer which will keep storing the elements and thus a new sorted linked list will be formed.
-
In the end just check if any element is left in the linked lists, if yes then add them to the new merged linked list and return head of new linked list.
Working of Code :
Let us take an example :-
Input two linked lists -
List 1 = 1 -> 2 -> 4
List 2 = 1 -> 3 -> 5
final_list = null
Compare first two nodes in both linked lists : [1,1] both are equal we can choose to add any of the two in the final_list and move head pointer of the choosen list, in this case we choose list 1 and move head pointer to next element
List 1 = 2 -> 4
List 2 = 1 -> 3 -> 5
final_list = 1
Compare first two nodes in both linked lists : [2,1] , 1 is smaller so add it to the final_list and move the pointer in list 2.
List 1 = 2 -> 4
List 2 = 3 -> 5
final_list = 1 -> 1
Compare the first two nodes in both linked lists : [2,3], 2 is smaller so add it to the final_list and move the pointer in list 1.
List 1 = 4
List 2 = 3 -> 5
final_list = 1 -> 1 -> 2
Compare the first two nodes in both linked lists : [4,3], 3 is smaller so add it to the final_list and move the pointer in list 2.
List 1 = 4
List 2 = 5
final_list = 1 -> 1 -> 2 -> 3
Compare the last two nodes in both linked lists : [4,5], 4 is smaller so add it to the final_list and move the pointer in list 1.
List 1 = NULL
List 2 = 5
final_list = 1 -> 1 -> 2 -> 3 -> 4
If any one of the two linked lists is pointing to NULL then simply add all the elements of other list in final_list.
final_list = 1 -> 1 -> 2 -> 3 -> 4 -> 5
Note :
We are not deleting the elements of the two linked lists, but as we move the head pointer to the next element in linked list we already lost the previous element because we now don't have any means to go back to previous element, remember in a singly linked list only the address of next element is stored but not the previous one.
Implementation :
//function takes two linked lists as input
node* merged_linkedlist(node* head1, node* head2) {
//Check if any linked list is empty
if (head1 == nullptr) {
return head2;
} else if (head2 == nullptr) {
return head1;
}
//head pointer for merged linked list
node* newhead = nullptr;
//check for smallest element by comparing first two elements
//of both linked lists
if (head1->data <= head2->data) {
newhead = head1;
//moving head 1 to point to next element in the
//linked list 1 for further comparison
head1 = head1->next;
} else {
newhead = head2;
//moving head 2 to point to next element in the
//linked list 2 for further comparison
head2 = head2->next;
}
//new pointer to move forward and store new elements and
//keeping head pointer of new linked list as it is
node* temphead = newhead;
//run the loop until we reach last element of both lists
while (head1 != nullptr && head2 != nullptr) {
node* temp = nullptr;
if (head1->data <= head2->data) {
temp = head1;
head1 = head1->next;
} else {
temp = head2;
head2 = head2->next;
}
//store the next element and move forward to new node
temphead->next = temp;
temphead = temp;
}
//if any element is left then add it to final linked list
if (head1 != nullptr) {
temphead->next = head1;
} else if (head2 != nullptr) {
temphead->next = head2;
}
return newhead;
}
Step 4 : Main function and Display function
- Write a main function to call the merged_linkedlist function.
- Wrtie a display function to print merged linked list.
void display(node* node1)
{
while (node1 != NULL) {
printf("%d ", node1->data);
node1 = node1->next;
}
}
int main()
{
//create linked list 1
node* head1 = newnode(1);
head1->next = newnode(3);
head1->next->next = newnode(5);
//print linked list 1
cout<<"linked list 1 - ";
display(head1);
//create linked list 2
node* head2 = newnode(0);
head2->next = newnode(2);
head2->next->next = newnode(4);
//print linked list 2
cout<<"linked list 2 - ";
display(head2);
//call merging function
node* head = merged_linkedlist(head1, head2);
//print merged linked list
cout<<"merged linked list - ";
display(head);
return 0;
}
Final Code :
#include<bits/stdc++.h>
using namespace std;
//defining node type using struct
struct node{
int data;
struct node* next;
};
//function to create new node
node* newnode(int key)
{
struct node* temp = new node;
temp->data = key;
temp->next =nullptr;
return temp;
}
node* merged_linkedlist(node* head1, node* head2) {
//Check if any linked list is empty
if (head1 == nullptr) {
return head2;
} else if (head2 == nullptr) {
return head1;
}
//head pointer for merged linked list
node* newhead = nullptr;
//check for smallest element by comparing first two elements
//of both linked lists
if (head1->data <= head2->data) {
newhead = head1;
//moving head 1 to point to next element in the
//linked list 1 for further comparison
head1 = head1->next;
} else {
newhead = head2;
//moving head 2 to point to next element in the
//linked list 2 for further comparison
head2 = head2->next;
}
//new pointer to move forward and store new elements and
//keeping head pointer of new linked list as it is
node* temphead = newhead;
//run the loop until we reach last element of both lists
while (head1 != nullptr && head2 != nullptr) {
node* temp = nullptr;
if (head1->data <= head2->data) {
temp = head1;
head1 = head1->next;
} else {
temp = head2;
head2 = head2->next;
}
//store the next element and move forward to new node
temphead->next = temp;
temphead = temp;
}
//if any element is left then add it to final linked list
if (head1 != nullptr) {
temphead->next = head1;
} else if (head2 != nullptr) {
temphead->next = head2;
}
return newhead;
}
void display(node* node1)
{
while (node1 != nullptr) {
cout<<node1->data<<" ";
node1 = node1->next;
}
cout<<endl;
}
int main()
{
//create linked list 1
node* head1 = newnode(1);
head1->next = newnode(3);
head1->next->next = newnode(5);
cout<<"linked list 1 - ";
display(head1);
//create linked list 2
node* head2 = newnode(0);
head2->next = newnode(2);
head2->next->next = newnode(4);
cout<<"linked list 2 - ";
display(head2);
node* head = merged_linkedlist(head1, head2);
cout<<"merged linked list - ";
display(head);
return 0;
}
Output :
linked list 1 - 1 3 5
linked list 2 - 0 2 4
merged linked list - 0 1 2 3 4 5
With this article at OpenGenus, you must have the complete idea of approaches to Merge two sorted linked lists.
