# 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

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

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