/* * Instructions: * * 1. Only complete the functions specified below. Do not create any additional function. * 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 reverseList(), rotateList() and partitionList() 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 reverses the input list by re-linking the nodes in * reverse order, and returns its new head. You should not create additional * nodes or copy the data in nodes. * */ node* reverseList(node* head) { }

/* * This function rotates the input list clockwisely by a half of its length * (i.e. floor(length/2) nodes) and returns its new head. * * Clockwise rotation means removing the tail node and inserting it at the front of the list. * */ node* rotateList(node* head) {

}

/* * The function partition the input list by using the first node as pivot. Nodes * smaller than pivot are moved before the pivot and nodes greater than the pivot * are moved after the pivot. Return the new head of the list, or return NULL if * the list is empty. * * Precondition: no duplicate keys (data) in the input list */ node* partitionList(node* head) {

}

//-------------------------- 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("tut05_input.txt"); if (!fin) { cout << "Input file not found."; exit(1); }

int testcase = 0; fin >> testcase;

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

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

node* list = ListHelper::newList(arr, n);

cout << "Case " << i + 1 << endl; cout << "Input:\t\t"; ListHelper::printList(list);

cout << "Reversed:\t"; list = reverseList(list); ListHelper::printList(list);

cout << "Rotated:\t"; list = rotateList(list); ListHelper::printList(list);

cout << "Partitioned:\t"; list = partitionList(list); ListHelper::printList(list); cout << endl;

ListHelper::deleteList(list); delete[] arr; }

return 0; }

please write in C++.

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

Text file contents given below

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

5 5 1 3 5 7 9 6 0 2 4 6 8 10 1 1 2 2 1 0

================================================================================ Below is the description of the input format and expected output. ================================================================================

Input: The first line of input contains an integer T denoting the number of test cases. The first line of each test case contains an integer N, which is the length of the list. The second line of each test case contains N integers separated with a space which are the data for the list.

Output: Case 1 Input: [1]-> [3]-> [5]-> [7]-> [9]-> NULL Reversed: [9]-> [7]-> [5]-> [3]-> [1]-> NULL Rotated: [3]-> [1]-> [9]-> [7]-> [5]-> NULL Partitioned: [1]-> [3]-> [9]-> [7]-> [5]-> NULL

Case 2 Input: [0]-> [2]-> [4]-> [6]-> [8]-> [10]-> NULL Reversed: [10]-> [8]-> [6]-> [4]-> [2]-> [0]-> NULL Rotated: [4]-> [2]-> [0]-> [10]-> [8]-> [6]-> NULL Partitioned: [0]-> [2]-> [4]-> [10]-> [8]-> [6]-> NULL

Case 3 Input: [1]-> NULL Reversed: [1]-> NULL Rotated: [1]-> NULL Partitioned: [1]-> NULL

Case 4 Input: [2]-> [1]-> NULL Reversed: [1]-> [2]-> NULL Rotated: [2]-> [1]-> NULL Partitioned: [1]-> [2]-> NULL

Case 5 Input: NULL Reversed: NULL Rotated: NULL Partitioned: NULL