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

Given two linked lists sorted in reverse order, write a function to merge them in such a way that the result list should be in reverse order

Example

INPUT
list1: 2->5->8->12
list2: 3->7->9

OUTPUT
result : 12->9->8->7->5->3->2

Method 1

A simple solution is to merge the both sorted lists and then reverse the merged list. But it requires two traversals.

Method 2

This method take O(1) auxiliary space and requires only one traversal

Algorithm

Traverse both lists till one of the list beomes null

1. Compare nodes in both lists, the node which has less value should be inserted at the beginning of the result list

2. If any list becomes NULL, then insert all the elements present in other list

C++ Program

``````#include <bits/stdc++.h>
using namespace std;

struct LLNode{
int data;
LLNode *next;
};
void insertAtBeginning(LLNode**,int );
// This function will merge the two sorted lists
//and returns the result which is in reverse order
LLNode* sortedMerge(LLNode *list1, LLNode *list2)
{
// If both lists are empty
if (list1==NULL && list2==NULL) return NULL;

// Initialize head of resultant list
LLNode *res = NULL;

// Traverse both lists till one of them becomes null
while (list1 != NULL && list2 != NULL)
{
//If list1 node data is less than or equal to list2 node data
if (list1->data <= list2->data)
{
insertAtBeginning(&res,list1->data);
list1 = list1->next;
}
else
{
insertAtBeginning(&res,list2->data);
list2 = list2->next;
}
}

//If list2 has finished and list1 is still remaining
while (list1 != NULL)
{
insertAtBeginning(&res,list1->data);
list1 = list1->next;
}

//If list1 has finished and list2 is still reaining
while (list2 != NULL)
{
insertAtBeginning(&res,list2->data);
list2 = list2->next;
}

return res;
}
{
LLNode*curr=new LLNode;
//make a new node with this data and next pointing to NULL
curr->data=dataToBeInserted;
curr->next=NULL;

if(*head==NULL) //if list is empty then set the current formed node as head of list

else //make the next of the current node point to the present head and make the current node as the new head
{
}

//O(1) constant time
}

{
while(temp!=NULL) //till the list ends (NULL marks ending of list)
{
if(temp->next!=NULL)
cout<<temp->data<<" ->";
else
cout<<temp->data;

temp=temp->next; //move to next node
}
//O(number of nodes)
cout<<endl;
}

int main()
{
LLNode *result = NULL;
LLNode *list1 = NULL; //initial list has no elements

insertAtBeginning(&list1,12);
insertAtBeginning(&list1,8);
insertAtBeginning(&list1,5);
insertAtBeginning(&list1,2);

LLNode *list2 = NULL;
insertAtBeginning(&list2,9);
insertAtBeginning(&list2,7);
insertAtBeginning(&list2,3);

cout<<"\n Two lists are :-\n";
cout<<"list1 is "<<endl;
display(&list1);

cout<<"List2 is"<<endl;
display(&list2);

result = sortedMerge(list1,list2);
cout<<"After merging two sorted lists "<<endl;
display(&result);
return 0;
}``````

Scroll to Top