How to merge two sorted lists into a reverse-ordered list in C++

Overview

In this Answer, we'll look at how to merge two lists sorted in ascending order such that the resultant list is in descending order in C++.

Algorithm

Let's assume that list1 and list2 are the input lists and list3 is the resultant linked list.

In our algorithm, we simply compare the heads from list1 and list2 and add the smaller ones at the head of list3. If one of the lists gets empty, we skip the comparison and simply remove the elements from the head of the second list and insert these at the head of list3. We repeat this until the second list also becomes empty.

This algorithm is repeated until all elements from list1 and list2 are inserted into list3.

The following image will help us better comprehend the concept:

1 of 5

Code

main.cpp
Node.h
#include<iostream>
#include "Node.h"
using namespace std;
/*merges two linked lists sorted in asc. order
into a resultant list sorted in desc. order.
@param headList1 pointer to list1 sorted in asc. order
@param headList2 pointer to list2 sorted in asc. order
@return pointer to merged list in desc. order
*/
Node *merge(Node *headList1, Node *headList2){
Node *headList3 = nullptr;
Node *currentList1 = headList1, *currentList2 = headList2;
/*until either or both linked lists are empty, find the smallest
element from list1 and list2 , remove it and insert it at the head
of list 3. This will create a desc. order list.*/
while(currentList1 != nullptr && currentList2 != nullptr){
if(currentList1->data < currentList2->data){
Node *nextCurrent = currentList1->next;
currentList1->next = headList3;
headList3 = currentList1;
currentList1 = nextCurrent;
} else {
Node *nextCurrent = currentList2->next;
currentList2->next = headList3;
headList3 = currentList2;
currentList2 = nextCurrent;
}
}
/*until list1 is empty, remove element from list1 and insert it at the head
of list 3*/
while(currentList1 != nullptr){
Node *nextCurrent = currentList1->next;
currentList1->next = headList3;
headList3 = currentList1;
currentList1 = nextCurrent;
}
/*until list2 is empty, remove element from list1 and insert it at the head
of list 3*/
while(currentList2 != nullptr){
Node *nextCurrent = currentList2->next;
currentList2->next = headList3;
headList3 = currentList2;
currentList2 = nextCurrent;
}
return headList3;
}
// list1 values in asc. order
int valuesList1[] = {1,3,5,7,9};
int lengthList1 = 5;
// list2 values in asc.order
int valuesList2[] = {2,4,6,8};
int lengthList2 = 4;

Time complexity analysis

The time complexity is O(M+N) where M and N are lengths of list1 and list2 respectively.

Explanation

  • Lines 22–26: When both list1 and list2 have values and currentList1->data contains the smallest value, the node pointed by currentList1 is inserted at the head of list3. Then, currentList1 points to its next element.
  • Lines 28–31: When both list1 and list2 have values and currentList2->data contains the smallest value, the node pointed bycurrentList2 is inserted at the head of list3. Then, currentList2 points to the next element.
  • Lines 38–41: When list2 is empty and no comparison is needed to find the smallest element, each element is removed from the head of list1 and inserted at the head of list3.
  • Lines 46–51: When list1 is empty and no comparison is needed to find the smallest element, each element is removed from the head of list2 and inserted at the head of list3.

Free Resources