Hi there, fellow geeks! In this article, let’s discuss how to merge 2 sorted linked lists LeetCode solution in a sorted manner.
Explanation of merge 2 sorted linked lists LeetCode problem:
We are given two non-empty single linked lists, sorted in ascending order, as input and the goal is to merge them in such a way that the resultant list is also sorted in ascending order. For example,
The first linked list, l1 is given as 4->7->10->NULL
And the second list, l2 is given as 5->6->7->12->20->NULL
Then the output is 4->5->6->7->7->10->12->20->NULL
l1:
l2:
Output:
Approach 1 (Using auxiliary sort function):
The first and most beginner-friendly idea to solve Merge 2 Sorted Linked Lists LeetCode problem that comes to mind is that we simply merge the two lists and then sort them accordingly. Easy right? We will iterate the first list to find its tail, and then link it to the head of the second list. After this is done, we will use a sorting function sort the resultant list. Below is an algorithm for the same, formulated for ease of understanding.
Algorithm:
00001. Set mergedHead = NULL.
00002. Iterate the first list till end is reached.
00003. For each node of this list create a new node in merged list and insert the element.
00004. Iterate the second list till end is reached.
00005. For each node of this list create a new node in merged list and insert the element.
00006. Sort the merged list.
00007. Return head of the merged list i.e. mergedHead.
Implementation in C:
//C program to merge two sorted linked list
#include<stdio.h>
#include<stdlib.h>
//structure of nodes
struct node{
int data;
struct node *next;
};
//auxiliary function to create linked list
struct node* createList(int arr[], int n){
struct node *head = NULL,*ptr;
for(int i=0;i<n;i++){
struct node *newNode = (struct node*)malloc(sizeof(struct node));
newNode->data = arr[i];
newNode->next = NULL;
if(head == NULL){
//first node
head = ptr = newNode;
}
else{
//other nodes
ptr->next = newNode;
ptr = ptr->next;
}
}
return head;
}
//auxiliary function to display list
void displayList(struct node *head){
struct node *ptr = head;
while(ptr != NULL){
printf("%d -> ", ptr->data);
ptr = ptr->next;
}
printf("NULLn");
}
//auxiliary function to return length of linked list
int listLength(struct node *head){
int count = 0;
struct node *ptr = head;
while(ptr != NULL){
count++;
ptr = ptr->next;
}
return count;
}
//bubble sort function for linked list
struct node* sortList(struct node **head){
int n = listLength(*head);
for(int i=0;i<n-1;i++){
struct node *curr = *head;
struct node *nex = curr->next;
for(int j=0;j<n-i-1;j++){
if(curr->data > nex->data){
//swapping the node data appropriately
int temp = curr->data;
curr->data = nex->data;
nex->data = temp;
}
curr = curr->next;
nex = curr->next;
}
}
return *head;
}
//function to merge two lists
struct node* mergeList(struct node *l1, struct node *l2){
struct node *ptr = l1;
while(ptr->next != NULL)
ptr = ptr->next;
//end of first list
ptr->next = l2;
struct node *head = l1;
head = sortList(&head);
return head;
}
//driver function
int main(){
//creation of first list
int arr1[] = {4, 7, 10};
int n = sizeof(arr1) / sizeof(int);
struct node *l1 = createList(arr1,n);
//creation of second list
int arr2[] = {5, 6, 7, 12, 20};
int m = sizeof(arr2) / sizeof(int);
struct node *l2 = createList(arr2, m);
//input lists
printf("List 1: ");
displayList(l1);
printf("List 2: ");
displayList(l2);
struct node *merged = NULL;
merged = mergeList(l1, l2);
//merged list
printf("Merged list: ");
displayList(merged);
return 0;
}Implementation in C++:
//C++ program merge two sorted lists
#include<iostream>
#include<vector>
using namespace std;
//class for linked list
class LinkedList{
public:
//class for node
class node{
public:
int data;
node *next;
};
//head pointer for linked list
node *head;
//constructor to initialize object
LinkedList(){
head = NULL;
}
//auxiliary member function to create list
void createList(vector<int> &vec){
int n = vec.size();
node *ptr;
for(int i = 0; i < n; i++){
node *newNode = new node;
newNode->data = vec[i];
newNode->next = NULL;
if(head == NULL){
head = ptr = newNode;
}
else{
ptr->next = newNode;
ptr = ptr->next;
}
}
}
//function to return length of list
int listLength(node *head){
int count = 0;
node *ptr = head;
while(ptr != NULL){
count++;
ptr = ptr->next;
}
return count;
}
//bubble sort function for linked list
node* sortList(node **head){
int n = listLength(*head);
for(int i=0;i<n-1;i++){
node *curr = *head;
node *nex = curr->next;
for(int j=0;j<n-i-1;j++){
if(curr->data > nex->data){
//swapping the node data appropriately
int temp = curr->data;
curr->data = nex->data;
nex->data = temp;
}
curr = curr->next;
nex = curr->next;
}
}
return *head;
}
//function to merge two lists
node* mergeList(node *l1, node *l2){
node *ptr = l1;
while(ptr->next != NULL)
ptr = ptr->next;
ptr->next = l2;
l1 = sortList(&l1);
return l1;
}
//auxiliary member function to display the linked list
void display(){
node *ptr = head;
while(ptr != NULL){
cout<<ptr->data<<" -> ";
ptr = ptr->next;
}
cout<<"NULL"<<endl;
}
};
int main(){
//using vector to insert elements into linked list
vector<int>vec1{4, 7, 10};
vector<int>vec2{5, 6, 7, 12, 20};
LinkedList list1;
list1.createList(vec1);
LinkedList list2;
list2.createList(vec2);
//input lists
cout<<"List 1: ";
list1.display();
cout<<"List 2: ";
list2.display();
LinkedList merged;
merged.head = merged.mergeList(list1.head, list2.head);
//output list
cout<<"Merged list: ";
merged.display();
}Analysis of the Algorithm:
This algorithm used to solve Merge 2 Sorted Linked Lists LeetCode problem is very easy to understand and write but it has some serious drawbacks. First of all, the time complexity of the original algorithm is O(n). But when we include sorting in this, the time complexity may increase depending upon the algorithm. Overall, this method takes a long time to execute. Hence, this approach is not very efficient. Moreover, this approach is not focused on the objective behind the question. So how can we reduce the time complexity? Is there a way to somehow solve this problem using only one iteration? Let’s discuss another approach to find out.
Approach 2 (Using iteration):
In this method, we will iterate both the lists simultaneously and compare each node. The node data that is smaller will get inserted into the new list. If both the nodes have same data, then two new nodes will be inserted into the new list. The idea behind this approach is that, the lists are to be merged in a sorted way and comparing the lists node by node is the best way to achieve that.
Algorithm:
00001. Set ptr1 = head1
00002. Set ptr2 = head2
00003. Repeat while ptr1 != NULL or ptr2 != NULL
00004. If (ptr1->data < ptr2->data), insert ptr1->data into mergedList
00005. ptr1 = ptr1->next
00006. Else if (ptr1->data > ptr2->data), insert ptr2->data into mergedList
00007. ptr2 = ptr2->next
00008. Else if (ptr1->data = ptr2->data), insert both into mergedList
00009. ptr1 = ptr1->next and ptr2 = ptr2->next (end of loop)
00010. If any list has not reached its end, link it with mergedList
Implementation in C:
//C program to merge two sorted linked list
#include<stdio.h>
#include<stdlib.h>
//structure of nodes
struct node{
int data;
struct node *next;
};
//auxiliary function to create linked list
struct node* createList(int arr[], int n){
struct node *head = NULL,*ptr;
for(int i=0;i<n;i++){
struct node *newNode = (struct node*)malloc(sizeof(struct node));
newNode->data = arr[i];
newNode->next = NULL;
if(head == NULL){
//first node
head = ptr = newNode;
}
else{
//other nodes
ptr->next = newNode;
ptr = ptr->next;
}
}
return head;
}
//auxiliary function to display list
void displayList(struct node *head){
struct node *ptr = head;
while(ptr != NULL){
printf("%d -> ", ptr->data);
ptr = ptr->next;
}
printf("NULLn");
}
//function to merge two sorted lists
struct node* mergeList(struct node *l1, struct node *l2){
struct node *head = NULL;
struct node *ptr1 = l1;
struct node *ptr2 = l2;
struct node *curr = NULL;
while(ptr1 != NULL && ptr2 != NULL){
struct node *new = (struct node *)malloc(sizeof(struct node));
new->next = NULL;
if(ptr1->data < ptr2->data){
new->data = ptr1->data;
ptr1 = ptr1->next;
}
else if(ptr1->data > ptr2->data){
new->data = ptr2->data;
ptr2 = ptr2->next;
}
else{
new->data = ptr1->data;
struct node *anotherNew = (struct node *)malloc(sizeof(struct node));
anotherNew->data = ptr2->data;
anotherNew->next = NULL;
new->next = anotherNew;Implementation in C++:
//C++ program merge two sorted lists
#include<iostream>
#include<vector>
using namespace std;
//class for linked list
class LinkedList{
public:
//class for node
class node{
public:
int data;
node *next;
};
//head pointer for linked list
node *head;
//constructor to initialize object
LinkedList(){
head = NULL;
}
//auxiliary member function to create list
void createList(vector<int> &vec){
int n = vec.size();
node *ptr;
for(int i = 0; i < n; i++){
node *newNode = new node;
newNode->data = vec[i];
newNode->next = NULL;
if(head == NULL){
head = ptr = newNode;
}
else{
ptr->next = newNode;
ptr = ptr->next;
}
}
}
//function to merge two sorted lists
node* mergeList(node *l1, node *l2){
node *head = NULL;
node *ptr1 = l1;
node *ptr2 = l2;
node *curr = NULL;
while(ptr1 != NULL && ptr2 != NULL){
node *newNode = new node;
newNode->next = NULL;
if(ptr1->data < ptr2->data){
newNode->data = ptr1->data;
ptr1 = ptr1->next;
}
else if(ptr1->data > ptr2->data){
newNode->data = ptr2->data;
ptr2 = ptr2->next;
}
else{
newNode->data = ptr1->data;
node *anotherNew = new node;
anotherNew->data = ptr2->data;
anotherNew->next = NULL;
newNode->next = anotherNew;
ptr1 = ptr1->next;
ptr2 = ptr2->next;
}
if(curr == NULL){
head = newNode;
curr = newNode;
}
else{
curr->next = newNode;
curr = curr->next;
}
}
//if end of first list is not reached
if(ptr1 != NULL){
node *temp = head;
while(temp->next != NULL)
temp = temp->next;
temp->next = ptr1;
}
//if end of second list is not reached
if(ptr2 != NULL){
node *temp = head;
while(temp->next != NULL)
temp = temp->next;
temp->next = ptr2;
}
return head;
}
//auxiliary function to display list
void displayList(){
node *ptr = head;
while(ptr != NULL){
cout<<ptr->data<<" -> ";
ptr = ptr->next;
}
cout<<"NULL"<<endl;
}
};
int main(){
//using vector to insert elements into linked list
vector<int>vec1{4, 7, 10};
vector<int>vec2{5, 6, 7, 12, 20};
LinkedList list1;
list1.createList(vec1);
LinkedList list2;
list2.createList(vec2);
//input lists
cout<<"List 1: ";
list1.displayList();
cout<<"List 2: ";
list2.displayList();
LinkedList merged;
merged.head = merged.mergeList(list1.head, list2.head);
//output list
cout<<"Merged list: ";
merged.displayList();
}
Analysis of the Algorithm:
This algorithm uses only one iteration that encompasses both the lists. Hence, the time complexity of this approach is O(n). It does not require any auxiliary space. Thus the space complexity is O(n), which includes only the new list.
Approach 3 (Using Recursion):
When sorting is asked, the solution can usually be derived using a recursive approach. The best and cleanest method of solving this question is by recursion. In this method, we write a function to manipulate the pointers of the originally given lists and link the nodes in a sorted way, all this while iterating the list recursively. The only drawback of this algorithm is that it uses system stack space and must be handled carefully to avoid errors. But once you figure out a good recursive algorithm, it is usually the best method to solve given question.
Algorithm:
00001. Declare a result node pointer and initialize it to NULL.
00002. If head1 is NULL, assign head1 to result and return result.
00003. If head2 is NULL, assign head2 to result and return result.
00004. Find out which node is smaller and assign its address to result.
00005. Recursively call the function, passing next pointer of the smaller node and assign the returned value to result->next.
00006. Return result.
Implementation in C++:
//C++ program merge two sorted lists
#include<iostream>
#include<vector>
using namespace std;
//class for linked list
class LinkedList{
public:
//class for node
class node{
public:
int data;
node *next;
};
//head pointer for linked list
node *head;
//constructor to initialize object
LinkedList(){
head = NULL;
}
//auxiliary member function to create list
void createList(vector<int> &vec){
int n = vec.size();
node *ptr;
for(int i = 0; i < n; i++){
node *newNode = new node;
newNode->data = vec[i];
newNode->next = NULL;
if(head == NULL){
head = ptr = newNode;
}
else{
ptr->next = newNode;
ptr = ptr->next;
}
}
}
//function to merge two sorted lists
//recursion
node* mergeList(node* head1, node* head2) {
node* result=NULL;
//if node doesn't exist
if(head1==NULL){
result=head2;
return result;
}
else if(head2==NULL){
result=head1;
return result;
}
//if node exists
if(head1->data<=head2->data){
result=head1;
result->next=mergeList(head1->next, head2);
}
else{
result=head2;
result->next=mergeList(head1, head2->next);
}
//return the sorted added node
return result;
}
//auxiliary function to display list
void displayList(){
node *ptr = head;
while(ptr != NULL){
cout<<ptr->data<<" -> ";
ptr = ptr->next;
}
cout<<"NULL"<<endl;
}
};
int main(){
//using vector to insert elements into linked list
vector<int>vec1{4, 7, 10};
vector<int>vec2{5, 6, 7, 12, 20};
LinkedList list1;
list1.createList(vec1);
LinkedList list2;
list2.createList(vec2);
//input lists
cout<<"List 1: ";
list1.displayList();
cout<<"List 2: ";
list2.displayList();
LinkedList merged;
merged.head = merged.mergeList(list1.head, list2.head);
//output list
cout<<"Merged list: ";
merged.displayList();
}Analysis of the Algorithm:
This algorithm used to solve the Merge two Sorted Linked Lists LeetCode problem uses recursion in a clever way to manipulate the next pointers to point to the node that is just larger than the current node. Thus it merges and sorts the lists in O(n) time and O(1) space. Please note that the only additional space this algorithm will take is that of the system stack.
Conclusion:
It can be concluded that the merge 2 sorted linked lists LeetCode problem can be solved by iterating both the lists, either using loops or by recursion. However, recursion has an edge over the other methods.
Frequently Asked Questions:
Q1. Can I do this with any other data structure, not just linked lists?
Ans. Yes, this can be done with any other data structure but it must be a linear data structure.
Q2. How can I check if two sorted linked lists are equal?
Ans. For two linked lists to be equal, all their nodes including their position, must be equal. Checking this condition is enough to see if two linked lists are equal.
Q3. Is there a faster way to merge two sorted linked lists?
Ans. The recursive algorithm mentioned above seems to be the fastest way to merge two sorted linked lists.
Q4. Can I use another sorting algorithm for my sort-merge algorithm, such as quicksort or bubble sort?
Ans. Yes, other algorithms can be used to sort-merge two linked lists. For example, quick sort.
Q5. How can I reverse an unsorted linked list in place and keep it updated in real time?
Ans. A simple way to reverse a linked list is by using a stack. To keep the list updated in real time, we can use double pointers instead of normal pointers.
Q6. How do I merge two sorted linked lists (in place)?
Ans. This can be done by simply linking the tail of the first list to the head of the second list.
Also Read : How To Reverse A Linked List In Groups Of Given Size
