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()
{
/* 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 -> NULLTime 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?
- Create a new head pointer to an empty linked list.
- Check the first value of both linked lists.
- Whichever node from L1 or L2 is smaller, append it to the new list and move the pointer to the next node.
- Continue this process until you reach the end of a linked list.
2. Can we transfer in both directions in a double linked list?
Generally, doubly linked lists consume more space for every node and therefore, causes more expansive basic operations such as insertion and deletion. However, we can easily manipulate the elements of the list since the list maintains pointers in both the directions (forward and backward).
3. Can you reverse a linked list?
The recursive approach to reverse a linked list is simple, just we have to divide the linked lists in two parts and i.e first node and the rest of the linked list, and then call the recursion for the other part by maintaining the connection.