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<stdio.h>
#include<stdlib.h>
#include <stddef.h>

struct Node
{
    int key;
    struct Node* next;
};
 
// Given two non-empty linked lists 'a' and 'b'
struct Node* SortedMerge(struct Node *a,struct Node *b)
{
    // If both lists are empty
    if (a==NULL && b==NULL) return NULL;
 
    // Initialize head of resultant list
    struct Node *res = NULL;
 
    // Traverse both lists while both of then
    // have nodes.
    while (a != NULL && b != NULL)
    {
        // If a's current value is smaller or equal to
        // b's current value.
        if (a->key <= b->key)
        {
            // Store next of current Node in first list
           struct Node *temp = a->next;
 
            // Add 'a' at the front of resultant list
            a->next = res;
            res = a;
 
            // Move ahead in first list
            a = temp;
        }
 
        // If a's value is greater. Below steps are similar
        // to above (Only 'a' is replaced with 'b')
        else
        {
            struct Node *temp = b->next;
            b->next = res;
            res = b;
            b = temp;
        }
    }
 
    // If second list reached end, but first list has
    // nodes. Add remaining nodes of first list at the
    // front of result list
    while (a != NULL)
    {
        struct Node *temp = a->next;
        a->next = res;
        res = a;
        a = temp;
    }
 
    // If first list reached end, but second list has
    // node. Add remaining nodes of first list at the
    // front of result list
    while (b != NULL)
    {
        struct Node *temp = b->next;
        b->next = res;
        res = b;
        b = temp;
    }
 
    return res;
}
 
/* Function to print Nodes in a given linked list */
void printList(struct Node *Node)
{
    while (Node!=NULL)
    {
        printf("%d ",Node->key);
        Node = Node->next;
    }
}
 
/* Utility function to create a new node with
   given key */
struct Node *newNode(int key)
{
    struct Node* temp =
           (struct Node*) malloc(sizeof(struct Node));
    temp->key = key;
    temp->next = NULL;
    return temp;
}
 
/* Driver program to test above functions*/
int main()
{
    /* Start with the empty list */
    struct Node* res = NULL;
 
    /* Let us create two sorted linked lists to test
       the above functions. Created lists shall be
         a: 5->10->15
         b: 2->3->20  */
    struct Node *a = newNode(5);
    a->next = newNode(10);
    a->next->next = newNode(15);
 
    struct Node *b = newNode(2);
    b->next = newNode(3);
    b->next->next = newNode(20);
 
    printf("List A before merge: \n");
    printList(a);
 
    printf("\nList B before merge: \n");
    printList(b);
 
    /* merge 2 increasing order LLs in decreasing order */
    res = SortedMerge(a, b);
 
    printf("\nMerged Linked List is: \n");
    printList(res);
 
    return 0;
}
#include<iostream>
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<<Node->data<<" -> ";
        Node = Node->next;
    }
    cout<<"NULL"<<endl;
}

/* Using this function we will creating a new list node */
Node *newNode(int data)
{
    Node *temp = new Node;
    temp->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: "<<endl;
    PrintingList(list1);
    cout<<"Original linked list 2: "<<endl;
    PrintingList(list2);
    result = MergeSortedReverse(list1, list2);
    cout<<"Merged list in reverse order: "<<endl;
    PrintingList(result);
    return 0;
}


class ReverseMerge 
{
	Node head; 
	Node a;
    Node b;

	/* Node Class */
	static class Node 
    {
        int data;
		Node next;

		Node(int d) 
        {
			data = d;
			next = null;
		}
	}
	void printlist(Node node) {
		while (node != null) {
			System.out.print(node.data + " ");
			node = node.next;
		}
	}
	Node sortedmerge(Node node1, Node node2) {
		
		// if both the nodes are null
		if (node1 == null && node2 == null) {
			return null;
		}
		// resultant node
		Node res = null;

		// if both of them have nodes present traverse them
		while (node1 != null && node2 != null) {

			// Now compare both nodes current data
			if (node1.data <= node2.data) {
				Node temp = node1.next;
				node1.next = res;
				res = node1;
				node1 = temp;
			} else {
				Node temp = node2.next;
				node2.next = res;
				res = node2;
				node2 = temp;
			}
		}
		while (node1 != null) {
			Node temp = node1.next;
			node1.next = res;
			res = node1;
			node1 = temp;
		}
		while (node2 != null) {
			Node temp = node2.next;
			node2.next = res;
			res = node2;
			node2 = temp;
		}

		return res;

	}

	public static void main(String[] args) {

		ReverseMerge list = new ReverseMerge();
		Node result = null;

		list.a = new Node(5);
		list.a.next = new Node(10);
		list.a.next.next = new Node(15);

		list.b = new Node(2);
		list.b.next = new Node(3);
		list.b.next.next = new Node(20);

		System.out.println("List a before merge :");
		list.printlist(list.a);
		System.out.println("");
		System.out.println("List b before merge :");
		list.printlist(list.b);

		// merge two sorted linkedlist in decreasing order
		result = list.sortedmerge(list.a, list.b);
		System.out.println("");
		System.out.println("Merged linked list : ");
		list.printlist(result);

	}
}

# Node of a linked list
class Node:
	def __init__(self, next = None, data = None):
		self.next = next
		self.data = data

def SortedMerge(a,b):

	if (a == None and b == None):
		return None

	res = None

	while (a != None and b != None):
	
		if (a.key <= b.key):

			temp = a.next
			a.next = res
			res = a
			a = temp

		else:
		
			temp = b.next
			b.next = res
			res = b
			b = temp
		
	while (a != None):
	
		temp = a.next
		a.next = res
		res = a
		a = temp
	
	while (b != None):
	
		temp = b.next
		b.next = res
		res = b
		b = temp
	
	return res

def printList(Node):

	while (Node != None):
	
		print( Node.key, end = " ")
		Node = Node.next
	
def newNode( key):

	temp = Node()
	temp.key = key
	temp.next = None
	return temp

res = None
a = newNode(3)
a.next = newNode(7)
a.next.next = newNode(10)
a.next.next.next = newNode(14)

b = newNode(12)
b.next = newNode(13)
b.next.next = newNode(15)

print( "Original linked list 1:")
printList(a)

print( "\nOriginal linked list 2:")
printList(b)

res = SortedMerge(a, b)

print("\nMerged list in reverse order:")
printList(res)

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.
[forminator_quiz id=”5091″]

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

Leave a Reply

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