# Merge 2 Sorted Linked Lists LeetCode Solution 2022

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:

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.

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){
for(int i=0;i<n;i++){
struct node *newNode = (struct node*)malloc(sizeof(struct node));
newNode->data = arr[i];
newNode->next = NULL;
//first node
}
else{
//other nodes
ptr->next = newNode;
ptr = ptr->next;
}
}
}

//auxiliary function to display list
while(ptr != NULL){
printf("%d -> ", ptr->data);
ptr = ptr->next;
}
printf("NULLn");
}

//auxiliary function to return length of linked list
int count = 0;
while(ptr != NULL){
count++;
ptr = ptr->next;
}
return count;
}

//bubble sort function for linked list
for(int i=0;i<n-1;i++){
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;
}
}
}

//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;
}

//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;

public:

//class for node
class node{
public:
int data;
node *next;
};

//constructor to initialize object
}

//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;
}
else{
ptr->next = newNode;
ptr = ptr->next;
}
}
}

//function to return length of list
int count = 0;
while(ptr != NULL){
count++;
ptr = ptr->next;
}
return count;
}

//bubble sort function for linked list
for(int i=0;i<n-1;i++){
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;
}
}
}

//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(){
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};
list1.createList(vec1);
list2.createList(vec2);

//input lists
cout<<"List 1: ";
list1.display();
cout<<"List 2: ";
list2.display();

//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:

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){
for(int i=0;i<n;i++){
struct node *newNode = (struct node*)malloc(sizeof(struct node));
newNode->data = arr[i];
newNode->next = NULL;
//first node
}
else{
//other nodes
ptr->next = newNode;
ptr = ptr->next;
}
}
}

//auxiliary function to display list
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 *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;

public:

//class for node
class node{
public:
int data;
node *next;
};

//constructor to initialize object
}

//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;
}
else{
ptr->next = newNode;
ptr = ptr->next;
}
}
}

//function to merge two sorted lists
node* mergeList(node *l1, node *l2){
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){
curr = newNode;
}
else{
curr->next = newNode;
curr = curr->next;
}
}

//if end of first list is not reached
if(ptr1 != NULL){
while(temp->next != NULL)
temp = temp->next;
temp->next = ptr1;
}

//if end of second list is not reached
if(ptr2 != NULL){
while(temp->next != NULL)
temp = temp->next;
temp->next = ptr2;
}

}

//auxiliary function to display list
void displayList(){
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};
list1.createList(vec1);
list2.createList(vec2);

//input lists
cout<<"List 1: ";
list1.displayList();
cout<<"List 2: ";
list2.displayList();

//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;

public:

//class for node
class node{
public:
int data;
node *next;
};

//constructor to initialize object
}

//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;
}
else{
ptr->next = newNode;
ptr = ptr->next;
}
}
}

//function to merge two sorted lists
//recursion
node* result=NULL;

//if node doesn't exist
return result;
}
return result;
}

//if node exists
}
else{
}

return result;

}

//auxiliary function to display list
void displayList(){
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};
list1.createList(vec1);
list2.createList(vec2);

//input lists
cout<<"List 1: ";
list1.displayList();
cout<<"List 2: ";
list2.displayList();

//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.

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

## The Ultimate Guide to Using JavaScript Object Keys

JavaScript is a versatile and powerful programming language used in web development to create interactive and dynamic web…

## The Best VS Code Extensions 2022: An Ultimate List (Updated!)

Do you want to be a better developer? Are you looking for extensions that will make your life…

## How to Start Freelancing & Get Profitable Clients?

How to Start Freelancing Get Profitable Clients? I’ve got an immense response from you guys within the last…