Answer to Question #236732 in C++ for Olivia

Question #236732
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.
1
Expert's answer
2021-09-16T13:03:02-0400
#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);
}

Need a fast expert's response?

Submit order

and get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!

Comments

No comments. Be the first!

Leave a comment

LATEST TUTORIALS
New on Blog
APPROVED BY CLIENTS