CS302 Assignment 1: Fun with linked lists Description Looks like your instructor would like to welcome you back to CS302 with a fun linked list assignment. Given a linked list, reverse the nodes of a...

Thank you for reading! I need some help and was wondering if I can get a quote.


CS302 Assignment 1: Fun with linked lists Description Looks like your instructor would like to welcome you back to CS302 with a fun linked list assignment. Given a linked list, reverse the nodes of a linked list k at a time and return its modified list. k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is. You may not alter the values in the list’s nodes, only nodes themselves may be changed. Figures 1 and 2 show the list before and after swapping each disjoint k size sublists to get a better idea. Figure 1: Before and after, list size 5 and k = 2 Figure 2: Before and after, list size 5 and k = 3 Linked List Class template class LL { struct node { type data; node * next; node * prev; }; public: LL(); ~LL(); void reverseKLists(int); void add(const type &); template friend std:: ostream& operator <(std:: ostream&,="" const="" ll="">&); private: void reverse(LL :: node*&, LL :: node *&); node * head; node * tail; }; Each member contains/performs the following 1 • struct node - every node in the linked list contains a data field and a next/previous pointers, thus this is a doubly linked list • node * head- pointer that points to the first node of the linked list • node * tail - pointer that points to the end node of the linked list • LL::LL() - default constructor that sets up an empty linked list, i.e. sets head and tail with NULL or nullptr • LL::~LL() - destructor, deallocates all the nodes from head to tail • void LL::reverseKLists(int k) - function that reverses all the disjoint sublists of size k in the linked list, as described in the first section of the handout • void LL::add(const type& item) - performs a tail insert of the linked list, sets the end node’s data field with item (the parameter of this function) • std::ostream& operator<(std::ostream& out,="" const="">& list) - friend function that over- loads the output operator, just outputs all the data values in the linked list starting from the head node to the tail node, refer to the sample output for details • void LL::reverse(LL::node*& leftEndPoint, LL::node*& rightEndPoint) - this function is optional (I called this function in reverseKLists(int)), this function reverses the linked list from leftEndPoint pointer to rightEndPoint pointer, these pointers were determined in the reverseKLists(int) function and then called this function and kept that process going until all k sublists where reversed, thus this function is called a total of roughly size_of_list / k number of times Contents of main In main you prompt for a list size which we will call n. You then create an object of type LL and add integers 1 to n into this list, then prompt for the k value. You then output the original list then output the list after having each disjoint size k sublsist reversed. You should re-prompt if the user does not enter a non negative number for n and k. Specifications • Comment your code and functions • When reversing the sublists, you need to rearrange the nodes, you cannot just simply swap the data fields of existing nodes (this makes the code for reversing the linked list harder but more efficient in the general case), you also cannot reconstruct each sublist by deallocating and reallocating nodes • Your code cannot have memory leaks Sample Run $ g++ Asst01.cpp $ ./a.out Enter n and k: hi bye Enter n and k: 7 0 Enter n and k: -8 0 Enter n and k: 10 2 Original List 2 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 Reversed list 2 -> 1 -> 4 -> 3 -> 6 -> 5 -> 8 -> 7 -> 10 -> 9 $ ./a.out Enter n and k: 10 3 Original List 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 Reversed list 3 -> 2 -> 1 -> 6 -> 5 -> 4 -> 9 -> 8 -> 7 -> 10 $ ./a.out Enter n and k: 10 10 Original List 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 Reversed list 10 -> 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 $ ./a.out Enter n and k: 10 5 Original List 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 Reversed list 5 -> 4 -> 3 -> 2 -> 1 -> 10 -> 9 -> 8 -> 7 -> 6 $ ./a.out Enter n and k: 10 1 Original List 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 Reversed list 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 $ ./a.out Enter n and k: 10 4 Original List 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 Reversed list 4 -> 3 -> 2 -> 1 -> 8 -> 7 -> 6 -> 5 -> 9 -> 10 3 $ ./a.out Enter n and k: 10 8 Original List 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 Reversed list 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 9 -> 10 Submission Compress your files (a file with your int main in a .cpp file and your header .h or .hpp file) into a .zip file and upload to the webcampus site by the deadline 4