/* * Instructions: * * 1. Only complete the functions specified below. Do not create any additional function. * 2. Use Visual Studio 2019 to build, test and run your code. * 3. Do not include any additional header or library. * 4. This is an exercise of linked list operations. Do not copy linked lists to arrays for manipulation. * 5. Implement the functions mergeList() and reMergeList() as specified below. * 6. All linked lists in this exercise are singly-linked, non-circular and without header node. * */

#include #include #include #include

using namespace std;

/* Linked list node */ struct node { int data; node* next; };

//-------------------------- functions to be implemented by you

/* * The function takes two lists, each of which is sorted in ascending order, and * iteratively merges them into one list with ascending order. The head of the merged list is * returned. * * Time complexity: O(n) * Space complexity: O(1) * */ node* mergeList(node* list1, node* list2) {

}

/* * The recursive function takes two lists, each of which is sorted in ascending order, and * recursively merges them into one list with ascending order. The head of the merged list is * returned. * * Time complexity: O(n) * Space complexity: O(n) * */ node* reMergeList(node* list1, node* list2) {

}

//-------------------------- functions prepared for you

/* * Helper class for creating/printing a list from an array. */ class ListHelper { public: // build a list based on array input static node* newList(int* arr, int n) {

node dummy = { n, NULL }; node* cur = &dummy; for (int i = 0; i < n; i++) { cur->next = new node({ arr[i], NULL }); cur = cur->next; } return dummy.next; // without dummy header }

//print nodes in a given linked list static void printList(node* list) { while (list != NULL) { printf("[%d]-> ", list->data); list = list->next; } cout << "NULL" << endl; }

//delete nodes in a given linked list static void deleteList(node* list) { node* temp; while (list != NULL) { temp = list; list = list->next; delete temp; } } };

/* * Driver program * * Read the test cases from the input file and use them to test * your functions' implementation. * */ int main(int argc, char** argv) {

ifstream fin("tut07_input.txt"); if (!fin) { cout << "Input file not found."; exit(1); }

int testcase = 0; fin >> testcase;

for (int i = 0; i < testcase; i++) {

int n1, n2; fin >> n1 >> n2;

int* arr1 = new int[n1]; for (int j = 0; j < n1; j++) fin >> arr1[j];

int* arr2 = new int[n2]; for (int j = 0; j < n2; j++) fin >> arr2[j];

cout << "Case " << i + 1 << endl;

node* list1 = ListHelper::newList(arr1, n1); cout << "List 1: \t"; ListHelper::printList(list1);

cout << "List 2: \t"; node* list2 = ListHelper::newList(arr2, n2); ListHelper::printList(list2);

cout << "Merged list: \t"; node* result1 = mergeList(list1, list2); ListHelper::printList(result1);

// re-create list1 and list2 list1 = ListHelper::newList(arr1, n1); list2 = ListHelper::newList(arr2, n2); cout << "Remerged list: \t"; node* result2 = reMergeList(list1, list2); ListHelper::printList(result2); cout << endl;

ListHelper::deleteList(result1); ListHelper::deleteList(result2); delete[] arr1; delete[] arr2; }

return 0; }

Please answer in C++.

-----------------------------------------------

Contents of txt.input given below

-----------------------------------------------

4 1 1 2 1 5 4 1 4 9 10 22 3 7 8 15 0 3 1 3 5 0 0

================================================================================

Input: The first line of input contains an integer T denoting the number of test cases. The first line of each test case contains two integers N1 and N2, which are the length for list1 and list2. The second line of each test case contains N1+N2 integers separated with a space which are the inputs for list1 and list2 respectively.

Output: Case 1 List 1: [2]-> NULL List 2: [1]-> NULL Merged list: [1]-> [2]-> NULL Remerged list: [1]-> [2]-> NULL

Case 2 List 1: [1]-> [4]-> [9]-> [10]-> [22]-> NULL List 2: [3]-> [7]-> [8]-> [15]-> NULL Merged list: [1]-> [3]-> [4]-> [7]-> [8]-> [9]-> [10]-> [15]-> [22]-> NULL Remerged list: [1]-> [3]-> [4]-> [7]-> [8]-> [9]-> [10]-> [15]-> [22]-> NULL

Case 3 List 1: NULL List 2: [1]-> [3]-> [5]-> NULL Merged list: [1]-> [3]-> [5]-> NULL Remerged list: [1]-> [3]-> [5]-> NULL

Case 4 List 1: NULL List 2: NULL Merged list: NULL Remerged list: NULL