  Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email  Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

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

Last Updated on November 30, 2022 by Prepbytes In this article, we will discuss one of the famed question “merge 2 sorted linked list in reverse order”. Merging two sorted linked list in a reverse order will make your hand stronger on data structures like linked lists. Let’s discuss our topic to merge 2 sorted linked list in reverse order.

## How To Merge 2 Sorted Linked List In Reverse Order

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.

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 To Merge 2 Sorted Linked List In Reverse Order

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 To Merge 2 Sorted Linked List In Reverse Order

• 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 To Merge 2 Sorted Linked List In Reverse Order    ## Code Implementation To Merge 2 Sorted Linked List In Reverse Order

```#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()
{
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);

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);
PrintingList(list1);
PrintingList(list2);
result = MergeSortedReverse(list1, list2);
cout<<"Merged list in reverse order: "<<endl;
PrintingList(result);
return 0;
}

```
```class ReverseMerge
{
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("");
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)

printList(a)

printList(b)

res = SortedMerge(a, b)

print("\nMerged list in reverse order:")
printList(res)
```
``````Output
3 -> 7 -> 10 -> 14 -> NULL
12 -> 13 -> 15 -> NULL
Merged list in reverse order:
15 -> 14 -> 13 -> 12 -> 10 -> 7 -> 3 -> NULL``````

Time Complexity To Merge 2 Sorted Linked List In Reverse Order: O(max(m,n)), where m, n are the size of Linked Lists.

This article has discussed the most efficient way to merge 2 sorted linked list in reverse order. One of the best ways to improve data structures is to practice data structures like linked lists regularly. Don’t stop here, our experts have made a set of linked list questions that will definitely help in boosting your DSA skills, you can checkout Prepbytes (Linked List).

## FAQ

1. How do you combine two linked lists in order?