Merge two sorted linked lists

Introduction

The linked list is one of the most important concepts to know while preparing for interviews. Having a good grasp of a linked list can be a huge plus point in coding interviews.

Problem Statement

In this problem, we will be given two sorted linked lists. We need to merge both lists such that the newly created list is also in sorted order.

Problem Statement Understanding

The problem statement is quite straightforward, we will be given two linked lists that are sorted in nature, and then we need to form a linked list using all the nodes of both linked lists such that the newly formed list is sorted in order.

Let's try to understand the problem with the help of examples.

  • Let the two sorted lists given to us be:

  • Now, the list that we need to return must contain all the nodes of both lists in sorted order.
  • So, the newly formed resultant list will be:

    Let’s take another example:
  • Let the two sorted lists given to us be 2→8→9→10→NULL and 11→13→17→NULL
  • For the above two sorted lists, the final linked list after merging will be 2→8→9→10→11→13→17→NULL
Some more examples

Sample Input 1:

  • list 1: 1→3→5→7
  • list 2: 2→4→6→8

Sample Output 1:
1→2→3→4→5→6→7→8

Sample Input 2:

  • list 1: 2→3→6→7→9
  • list 2: 1→5→8→11→19→31

Sample Output 2:
1→2→3→5→6→7→8→9→11→19→31

Now, I think from the above examples, the problem statement is clear. Let’s see how we can approach it.

Before moving to the approach section, try to think how you can approach this problem.

  • If stuck, no problem, we will thoroughly see how we can approach this problem in the next section.

Let’s move to the approach section.

Approach 1

  • We will make a recursive function that will create a sorted list out of two given sorted lists, containing all the nodes of both the given sorted list.
  • We will compare the head of both the lists and the one with a smaller head will be appearing at the current position and all other nodes will appear after that.
  • Now we will call the recursive function for the rest of the remaining nodes, and then we will attach the current node with the result from the recursive call, i.e., with the remaining node’s result.
  • If any one of the nodes is NULL, then we need to return the other list’s head from there.

Time Complexity: O(n), n is the number of nodes in both the list combined.
Space Complexity: O(n), n is the size of the recursive stack

The above approach works fine, but can we make our code more efficient in terms of memory.

  • The answer is yes, and to know how we can reduce the space complexity, read the below approach which uses constant memory.

Let’s jump to the next approach.

Approach 2

  • In this approach, we first reverse both the lists given to us as input.
  • Then we will create an empty list result.
  • We will initialize two pointers h1 and h2 to the head of list 1 and list 2, respectively.
  • Then we will iterate over both the lists while(h1 != NULL && h2!=NULL).
    • While iterating at every step, we will find the larger of the two h1 and h2 by comparing h1→data and h2→data.
    • We will insert the larger one of h1 and h2 at the front of the result list.
    • Then we will move ahead in the list whose node was larger (larger node - we will compare using h1→data and h2→data).
  • If any of the h1 or h2 becomes NULL, we will insert all the remaining node’s of the other list into the result list.
  • At last, we will have a new list that will be sorted given by result.

Time Complexity: O(n), n is the number of nodes in both the list combined.
Space Complexity: O(1)

The above approach uses constant space, but it will iterate on both lists two times in the worst case.

  • First, when the list is reversed and the second time when we are iterating to sort the list.

Can we do even better?

  • The answer is yes, and to know the solution, read the below approach.

Approach 3

  • In this approach, we create a dummy node with INT_MIN value that will represent the tail of our new list.
  • Then we will iterate on both the lists while both of them is not NULL.
  • Then we need to check the node with a smaller value and insert it after the tail of our new list, and then update the tail of the list.
  • At last, If the first list has reached NULL, then we need to attach the remaining elements of the second list after the tail and vice versa.

Algorithm

  • Create a node named dummy having INT_MIN as its data.
  • Initialize a pointer named tail with the address of the above-created dummy variable.
  • Initialize two pointers named l1 and l2 with the heads of both the lists, respectively.
  • Until both l1 and l2 are not equal to NULL, run a while loop in which we need to check which pointer points to a smaller node.
    • If l1 points to a smaller node, we need to attach l1 at the end of the tail and update l1 with its next node’s address.
    • If l2 points to a smaller node, we need to attach l2 at the end of the tail and update l2 with its next node’s address
    • Then, we need to advance the tail pointer to its next node
  • After the while loop ends, we need to check whether l1 or l2 is NULL or not.
    • If l2 is NULL, we need to assign tail→next to l1.
    • If l1 is NULL, we need to assign tail→next to l1.
  • Finally, we return the dummy node’s next node as the head of our newly created list.

Dry Run

Code Implementation

#include 
#include
using namespace std;

/* Class with constructor for a node of Linked list */
class Node {
    public:
    int data;
    Node* next;
    // constructor
    Node(int x){
        data = x;
        next = NULL;
}
};

/* Using this function we will be printing the data of the linked list */
void print(Node* head)
{
    Node* curr = head;
    while (curr != NULL) {
        cout << curr->data << " -> ";
        curr = curr->next;
    }
    cout<<"NULL"<data < l2->data) {
                tail->next = l1;
                l1 = l1->next;
            } else {
                tail->next = l2;
                l2 = l2->next;
            }
            tail = tail->next;
        }

        tail->next = l1 ? l1 : l2;
        return dummy.next;
    }


/* Main function */
int main()
{
    Node *list1 = new Node(2);
    list1->next = new Node(3);
    list1->next->next = new Node(5);
    list1->next->next->next = new Node(9);

    Node *list2 = new Node(1);
    list2->next = new Node(4);
    list2->next->next = new Node(8);
    
    cout<<"Original linked list 1: "<

						 

Output

Original linked list 1:
2 -> 3 -> 5 -> 9 -> NULL
Original linked list 2:
1 -> 4 -> 8 -> NULL
Merged sorted linked list:
1 -> 2 -> 3 -> 4 -> 5 -> 8 -> 9 -> NULL

Time Complexity: O(n), where n is the total number of nodes in both the lists.

So, in this blog, we have tried to explain how you can merge two sorted linked lists in the most optimal way. This is a basic problem and is good for strengthening your concepts in LinkedList and if you want to practice more such problems, you can checkout Prepbytes (Linked List).

Previous post An interesting method to print the reverse of a linked list.
Next post Merge two sorted linked lists such that the merged list is in reverse order

Leave a Reply

Your email address will not be published. Required fields are marked *