Merge two sorted linked lists such that the merged list is in reverse order

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 are given two sorted linked lists, and we are asked to merge the two lists in such a way that the new merged list is in reverse order.

Problem Statement Understanding

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

If the given linked lists are:
list 1: 3→7→10→14.
list 2: 12→13→15.

• According to the problem statement, we need to merge the list 1 and list 2 in such a way that the final merged list is in the reverse order.
• When we actually merge the list 1 and list 2, our merged list will be 3→7→10→12→13→14→15.
• And our output will be the reverse of this merged list, which is 15→14→13→12→10→7→3.

Taking another example, if the linked lists are:
list 1: 1→2→3→9.
list 2: 4→5→11→17.

• In this case, when we merge list 1 and list 2, our merged list will be 1→2→3→4→5→9→11→17.
• And our output will be the reverse of this merged list, which is: 17→11→9→5→4→3→2→1.

Some more examples

Sample Input 1:

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

Sample Output 1:

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

Sample Input 2:

• list 1: 2→5→10→15
• list 2: 3→6→7

Sample Output 2:

• 15→10→7→6→5→3→2

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.

Well, the most naive idea is:

• Reverse the first list.
• Reverse the second list.
• And then merge two reversed linked lists.
  Using these above steps, we will get our required output.

Another similar approach is first to merge both the list and then finally reverse the merged list.

Both of the above approaches will work fine, but can we do this with some in-place algorithm and only one traversal using O(1) extra space?

• Let’s see the approach for the same.

Let’s move to the approach section.

Approach

This approach is based on a merge style process.

• First, we initialize the resultant linked list as empty.
• And then, traverse both the linked lists from beginning to end and compare the current nodes of both the linked lists and insert the smaller of two at the beginning of the resultant linked list.
• Finally, our resultant linked list will have the merged list in reverse order.

The following algorithm will explain the approach in detail.

Algorithm

• First, initialize the resultant linked list result as an empty list.
• Let h1 and h2 be the two pointers pointing to the head of list 1 and list 2, respectively.
• Now we will traverse the two given linked lists while(h1!=NULL && h2!=NULL).
  • We will find the smaller of two nodes pointed by h1 and h2.
  • After finding the smaller of the two nodes, we will insert the node with the smaller value at the front of the result list.
  • Then we will move forward in the linked list with a smaller node value.
• If either of the linked lists is traversed completely, then insert all the remaining nodes of another list into the result list.
• Finally, after all these steps, we will have our merged list in reverse order.

Dry Run

Code Implementation

#include
using namespace std;

/* Node structure of linked list node */
struct Node
{
    int data;
    struct Node* next;
};

/* Using this function we will be merging both the linked list in such a way that merged list will be in reverse order */
Node* MergeSortedReverse(Node *h1, Node *h2)
{
    if (h1==NULL && h2==NULL) return NULL;
    Node *result = NULL;
    while (h1 != NULL && h2 != NULL)
    {
        if (h1->data <= h2->data)
        {
            Node *temp = h1->next;
            h1->next = result;
            result = h1;
            h1 = temp;
        }
        else
        {
            Node *temp = h2->next;
            h2->next = result;
            result = h2;
            h2 = temp;
        }
    }
    while (h1 != NULL)
    {
        Node *temp = h1->next;
        h1->next = result;
        result = h1;
        h1 = temp;
    }
    while (h2 != NULL)
    {
        Node *temp = h2->next;
        h2->next = result;
        result = h2;
        h2 = temp;
    }

    return result;
}

/* Using this function we will be printing the linked list content */
void PrintingList(struct Node *Node)
{
    while (Node!=NULL)
    {
        cout<data<<" -> ";
        Node = Node->next;
    }
    cout<<"NULL"<data = data;
    temp->next = NULL;
    return temp;
}

int main()
{    struct Node* result = NULL;
    Node *list1 = newNode(3);
    list1->next = newNode(7);
    list1->next->next = newNode(10);
    list1->next->next->next = newNode(14);

    Node *list2 = newNode(12);
    list2->next = newNode(13);
    list2->next->next = newNode(15);
    cout<<"Original linked list 1: "<

						 

Output

Original linked list 1:
3 -> 7 -> 10 -> 14 -> NULL
Original linked list 2:
12 -> 13 -> 15 -> NULL
Merged list in reverse order:
15 -> 14 -> 13 -> 12 -> 10 -> 7 -> 3 -> NULL

Time Complexity: O(max(m,n)), where m, n are the size of Linked Lists.

This blog tried to discuss how you can merge two sorted linked lists such that the merge list is in the reversed order with no extra space and linear time complexity. 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).