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

**Contents**show

**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("NULL\n"); } //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