This exercise is to create a function to merge two sorted list of integers so th

Question

This exercise is to create a function to merge two sorted list of integers so that the resulted list is also sorted. Your function should take two call-by-reference arguments that are head pointers to two integer lists sorted in ascending order. Name the pointer arguments head1 and head2. After merging the lists, your function should return the head pointer of the newly merged list. The merged list must contain all nodes from the two original lists. At the end of the function call, the two original pointers head1 and head2 should have NULL values. Your function MUST NOT create or destroy any nodes in order to merge the lists. You may use the LinkedList implemented in assignment 4 to create two sorted lists. Write a test program to show that your function works as expected.

Hello, I need help. need assp. Need to be complete in c++ format. Thanks in advance

Explanation / Answer

// C++ merge two sorted list
#include <iostream>
#include <stdio.h>
#include <stdlib.h>

using namespace std;

struct node
{
int value;
struct node* next;
};

struct node* mergeSorted(struct node* listA, struct node* listB)
{
struct node* result = NULL;

if (listA == NULL)
return(listB);
else if (listB==NULL)
return(listA);

if (listA->value <= listB->value)
{
result = listA;
result->next = mergeSorted(listA->next, listB);
}
else
{
result = listB;
result->next = mergeSorted(listA, listB->next);
}
return(result);
}

// push element in list
void push(struct node** head, int newInput)
{
struct node* nodee = (struct node*) malloc(sizeof(struct node));
nodee->value = newInput;
nodee->next = (*head);
(*head) = nodee;
}

// print list
void displayList(struct node *node)
{
while (node!=NULL)
{
cout << node->value << " ";
node = node->next;
}
}

int main()
{

struct node* mergedList = NULL;
struct node* listA = NULL;
struct node* listB = NULL;

push(&listA, 15);
push(&listA, 11);
push(&listA, 8);
push(&listA, 6);
push(&listA, 3);
push(&listA, 1);
cout << " ListA: ";
    displayList(listA);

push(&listB, 20);
push(&listB, 17);
push(&listB, 14);
    push(&listB, 10);
push(&listB, 7);
push(&listB, 5);
cout << " ListB: ";
    displayList(listB);

mergedList = mergeSorted(listA, listB);

cout << " Merged List: ";
displayList(mergedList);

return 0;
}

/*
output:

ListA: 1 3 6 8 11 15
ListB: 5 7 10 14 17 20
Merged List: 1 3 5 6 7 8 10 11 14 15 17 20

*/

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.