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;
}
void insertAtBeginning(LLNode**head,int dataToBeInserted)
{
	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
			*head=curr;
		
	else //make the next of the current node point to the present head and make the current node as the new head
		{
			curr->next=*head;
			*head=curr;
		}
		
		//O(1) constant time
}


void display(LLNode**head)
{
	LLNode*temp=*head;
	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;
}

 

Translate ยป