Question

Consider two sorted linked lists L1 and L2, both containing integers in increasing order. Merge
these two lists into one list L3 such that L3 should also be sorted but in decreasing order. For
example L1 (1, 3, 5, 6) and L2 (2, 4, 8, 9) are merged into a list L3 (9, 8, 6, 5, 4, 3, 2, 1). We do
not know the size of lists L1 and L2. Add the function to Task 1.

Answer 1

#include<iostream>
using namespace std;
struct List{
	int data;
	List * next;
};


void sortedInsert(List** head, List* newNode)
{
    List* currentNode;
    
    if (*head == NULL|| (*head)->data>= newNode->data) {
        newNode->next = *head;
        *head = newNode;
    }
    else {
       
        currentNode = *head;
        while (currentNode->next != NULL
&& currentNode->next->data
< newNode->data) {
            currentNode = currentNode->next;
        }
        newNode->next = currentNode->next;
        currentNode->next = newNode;
    }
}
List* newNode(int data)
{
   
    List* node = new List();
 
    
    node->data = data;
    node->next = NULL;
 
    return node;
}
void displayList(struct List * node){
	while(node != NULL){
		cout<<node->data<<"  ";
		node = node->next;
	}
}


void printLists(List* node)
{
    
    if (node == NULL)
    return;
 
    
    printLists(node->next);
 
    
    cout << node->data << " ";
}
 
void merge(struct List * list1, struct List * list2){
	struct List *list3 = NULL; 
	while(list1 !=NULL){
		int item = list1->data;
	List * new_node = newNode(item);
    sortedInsert(&list3, new_node);
		
		list1= list1->next;
	}
	while(list2 !=NULL){
		int item = list2->data;
	List * new_node = newNode(item);
    sortedInsert(&list3, new_node);
		list2= list2->next;
	}
	printLists(list3);
}




int main(){
	struct List * list1 = NULL;
	List * node = newNode(1);
    sortedInsert(&list1, node);
     node = newNode(3);
    sortedInsert(&list1,node);
     node = newNode(5);
    sortedInsert(&list1, node);
     node = newNode(6);
    sortedInsert(&list1, node);
	
	cout<<"List 1 contains\n";
	displayList(list1);


struct List * list2 = NULL;
	 node = newNode(2);
    sortedInsert(&list2,node);
    node = newNode(4);
    sortedInsert(&list2, node);
    node = newNode(8);
    sortedInsert(&list2, node);
    node = newNode(9);
    sortedInsert(&list2, node);
	
	cout<<"\nList 2 contains\n";
	displayList(list2);
	cout<<"\nList 3 contains\n";
	merge(list1, list2);
}