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++.
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:
#include<iostream>#include "Node.h"using namespace std;/*merges two linked lists sorted in asc. orderinto 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 smallestelement from list1 and list2 , remove it and insert it at the headof 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 headof 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 headof list 3*/while(currentList2 != nullptr){Node *nextCurrent = currentList2->next;currentList2->next = headList3;headList3 = currentList2;currentList2 = nextCurrent;}return headList3;}// list1 values in asc. orderint valuesList1[] = {1,3,5,7,9};int lengthList1 = 5;// list2 values in asc.orderint valuesList2[] = {2,4,6,8};int lengthList2 = 4;
The time complexity is O(M+N) where M and N are lengths of list1
and list2
respectively.
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.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.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
.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
.