- May 15, 2020

a c b 1 2 3 4 5 start Quiz #2: Linked Lists and Recursion ICS-46 Fall 2019 Name ____________________ When working on this quiz, recall the rules stated on the Academic Integrity statement that you signed. You can download/unzip the q2helper project folder (available for Friday, on the Weekly Schedule link) in which to write/test/debug your code. Submit your completed q2solution.hpp file online by Thursday at 11:30pm; submit this sheet at the start of class on Friday. I will post my solutions to EEE reachable via the Solutions link on Friday afternoon. Write your answer to Problem 1 on this sheet. Print just the first page of this document and submit it in class. 1. (7 pts) Examine the mystery method and hand simulate the call mystery(start); using the linked list below. Use the non-templated LN class on the right. Cross out ALL references that are replaced and Write in new references: don’t erase any references. It will look a bit messy, but be as neat as you can. Probably it is best to do this problem first on another sheet of paper, the copy EVERYTHING here. If an assignment doesn’t change a pointer (e.g., x = x;) , just leave it as is: don’t cross it out and redraw it. void mystery(LN* a) { LN *b = a->next, *c = b->next; while (a->next->next != nullptr) { a->next = b->next; b->next = c->next; c->next = b; a = c; c = b->next; b = a->next; } } class LN { public: //Constructors…not needed int value; LN* next; } 2. (6 pts) Define a recursive function named relation; it is passed two std::string arguments; it returns one char value: ‘’ indicating the relationship between the first and second parameters. Hint: my code used no variable other than the parameters, compared strings to the empty string, and compared one character in one string to one character in the other. You may use C++relational operators only to compare single characters, otherwise this function would be trivial to write. Given the standard templated declaration for LN: template class LN { public: LN () : next(nullptr){} LN (const LN& ln) : value(ln->value), next(ln->next){} LN (T v, LN* n = nullptr) : value(v), next(n){} T value; LN* next; }; The remove_pairs functions are void and have one parameter: a linked list whose values appear in any order (and may be repeated); when finished, the linked list is in the same order, with pairs of adjacent values removed from the list (and returned to free storage using delete). For example, if l is a linked list printing as 1->2->2->3->nullptr; calling remove_pairs(l); and then printing the linked list l produces 1->3->nullptr. If l were 1->2->2->2->3->nullptr the result would be 1->2->3->nullptr; and if l were 1->2->2->2->2->3->nullptr the result would be 1->3->nullptr again. After one pair of values is removed, remaining subsequent pairs must be removed as well, but an odd number of the same values in-a- row will leave one present in the list. The driver/Googletests call these functions for duplicate pairs values at the front/middle/rear of the list, including adjacent duplicate pairs in all those locations. 3. (6 points) Write the remove_pairs _i function (remove_pairs iteratively). Its parameter should be a reference to a pointer. You might want to (also) try writing this function using a pointer to a pointer. The size of the body can be reduced, because it does not require separate code for removing pairs at the front and at the middle/end of the list. 4. (6 points) Write the remove_pairs _r function (remove_pairs recursively). Its parameter should be a reference to a pointer. You might want to try writing this function first, because it can be written compactly.