Merge 2 Sorted Linked Lists LeetCode Solution 2022

Merge 2 Sorted Linked Lists LeetCode

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("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