Merge two sorted linked lists (in-place)

Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

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

Note: Remember that we cannot use any extra space, as we need to do this in place.

Let's try to understand it more clearly using 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 list should 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→2→5→10→NULL
  • list 2: 3→7→9→11→NULL

Sample Output 1: 1→2→3→5→7→9→10→11→NULL

Sample Input 2:

  • list 1: 2→3→9→10→NULL
  • list 2: 4→5→7→8→12→NULL

Sample Output 2: 2→3→4→5→7→8→9→10→12→NULL

At this point, we have understood the problem statement. Now we will try to formulate an approach for this problem.

  • Before moving to the approach section, try to think about 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

Our approach will be simple:

  • We will make a recursive function that will create a sorted list out of two given sorted lists.
  • If both the heads of the linked lists are NULL, return NULL and if only one head is NULL, then return the other head.
  • 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 call the recursive function again with parameters as the next node of the list having a smaller head value and the head of the other list.
  • Our recursive call will be returning the next smaller element of the linked lists attached with the rest of the sorted list. Make next of current node point to the list returned by the recursive function (curr_node->next = recursiveFunction()).

Following all the above steps, we will have our merged sorted list containing nodes of all the given linked list in sorted order.

Algorithm 1

1) The recursive function will have two parameters, i.e., head1 and head2, denoting the current head node of the first and second list, respectively.
2) Base case:

  • If both of the head nodes are NULL, return NULL from there.
  • If one of the head nodes is NULL, but the other one is not NULL, return the other head.
    3) If head1’s data is less than head2’s data, assign head1’s next to the result returned by the recursive function having parameters head1→next and head2 and then return head1.
    4) Else, assign head2’s next to the result returned by the recursive function having parameters head1 and head2→next and then return head2.

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

  • The answer is yes, and to know it, have a look at the helpful observations and also read the below approach which uses constant memory.

Helpful Observations

  • If we observe, we can see that we need two pointers at the beginning of both the list, since the smallest value will be present at the beginning of both the lists.
  • The list has a smaller first node that will be considered as the first list and the other one would be considered the second list.
  • We then have to just insert the second pointer node between the first and its next node if its value lies between the first and its next node.
  • If that is not the case, then we just need to move forward in iteration.

Applying the above observations, we can easily create the new sorted linked list.

Approach 2

Taking help from the observation explained above, let us understand the approach with the help of an example.

  • Let the input lists be 1→4→7→10→NULL and 2→3→22→NULL
  • We would keep two pointers - one at the starting of each linked list.
  • Now, the first pointer will point to ‘1’ because the first list has a smaller first node, and the second one will point to ‘2’ because it has a greater first node.
  • Since the second pointer’s data lies between ‘1’ and ‘4’ (first pointer’s data and next of first pointer’s data), so we insert it between ‘1’ and ‘4’.
  • After inserting the second node, we update the head of the second list to its next node.
  • Now let’s suppose the value of the second pointer was greater than ‘4’ so, we would not do anything in this case and just move our first pointer forward by one node.

Now, let’s formulate an algorithm based on the approach discussed above and handle the edge cases that might be present while implementing the code.

Algorithm 2

  • Find which list has a smaller first node and consider it as the first list and the other one as the second list (flist stands for first list and slist stands for second list).
  • Now, initialize four pointers:
    • First will point to the head of the first list ( say flist_curr ).
    • The second will point to the second node of the first list ( say flist_next ).
    • The third will point to the head of the second list ( say slist_curr ).
    • The Fourth will point to the second node of the second list ( say slist_next ).
  • While iterating through the lists, we need to check if slist_curr’s value lies between flist_curr’s value and flist_next’s value.
    a) If its value lies in between, then we need to insert the slist_curr node in between flist_curr and flist_next and update flist_curr to slist_curr and slist_curr to slist_next.
    b) Else, we will check if there are more nodes in the first list.

    • If there are more nodes in the first list, then just move flist_curr and flist_next to their respective next nodes.
    • If that is not the case, then the last node of the first node should point to the remaining nodes of the second list, and then finally, we will return the head of the first list.
  • After performing the above steps, we would get our new list that is sorted.

Dry Run



Code Implementation

#include
using namespace std;
class Node
{
    public:
    int data;
    Node* next;
    Node(int x){
        data = x;
   next = NULL;
    }
};


void printList(Node *head)
{
    if (!head)
        return;
     
    while (head->next != NULL)
    {
        cout << head->data << " -> ";
        head = head->next;
    }
    cout << head->data << endl;
}
 
Node* mergeTwoSortedLists(Node* head1, Node* head2)
{
    // if first list has only one node
    if (!head1->next) {
        head1->next = head2;
        return head1;
    }
    // make the list with smaller first node as first list
    if((head1->data) > (head2->data)){
        Node *temp = head1;
        head1 = head2;
       head2 = temp;
    }
    // Initialize all four pointer as discussed above in step 1 
    Node *flist_curr = head1, *flist_next = head1->next;
    Node *slist_curr = head2, *slist_next = head2->next;
 
    while (flist_next && slist_curr) {
        // if value of slist_curr lies in between value of flist_curr and
        // value of flist_next then insert slist_curr between flist_curr and 
        // flist_next
        if ((slist_curr->data) >= (flist_curr->data) && (slist_curr->data) <= (flist_next->data)) {
            slist_next = slist_curr->next;
            flist_curr->next = slist_curr;
            slist_curr->next = flist_next;
 
            // update flist_curr to point to slist_curr and slist_curr to point to slist_next
            flist_curr = slist_curr;
            slist_curr = slist_next;
        }
        else {
            // if we have not reached end of first list
            if (flist_next->next) {
                flist_next = flist_next->next;
                flist_curr = flist_curr->next;
            }
 
            // if we have reached the end of the first list then 
            // point last node’s next to remaining nodes of 
            // second list
            else {
                flist_next->next = slist_curr;
                return head1;
            }
        }
    }
    return head1;
}
 
int main(void)
{
    Node* head1 = NULL;
    head1 = new Node(1);
    head1->next = new Node(4);
    head1->next->next = new Node(7);
    head1->next->next->next = new Node(10);
 
    Node* head2 = NULL;
    head2 = new Node(2);
    head2->next = new Node(3);
    head2->next->next = new Node(22);
 
    Node *tmp = mergeTwoSortedLists(head1,head2);
    cout<<"Merged Linked list"<

						 

Output

Merged Linked list
1 -> 2 -> 3 -> 4 -> 7 -> 10 -> 22

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

So, in this blog, we have tried to explain how you can merge two sorted linked lists (in-place) in the most optimal way. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Previous post Create a Doubly Linked List from the given Ternary Tree
Next post Reverse a Doubly Linked List using recursion

Leave a Reply

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