Competitive Programming, Problems, Programming Questions

Merge 2 Sorted Linked Lists (LeetCode Solution)

14 min read
Merge 2 Sorted Linked Lists

Hi there, fellow geeks! In this article, let’s discuss how to merge 2 sorted linked lists in a sorted manner.

Explanation:

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


Leave a Reply

Your email address will not be published.

Sign up for our Newsletter

Get all the latest updates on what’s happening in the tech & startup world, delivered straight to your inbox from us.

Related Posts