cpp/recursion/monkey_reverse Source

Viewing cpp/recursion/monkey_reverse by daveagp@gmail.com. You have unsaved changes. Log in above to create, edit, preview and publish Websheets.

Property Value

Description
html markup
shown to student

Using recursion,
create a method <tt>reverse()</tt>
that reverses the elements in a linked list.
You will need to declare and define a helper function.

Epilogue
html markup
shown when solved

remove
Public permissions remove
Remarks
Comments, history, license, etc.

remove
Engine
Choices
json list of string, bool pairs
e.g. [["good", true], ["bad", false]]

Correct answer
Template / Reference solution

Template / Reference solution

#include <iostream>
#include <string>
using namespace std;

// structure of items in list
struct Node {
Node* next; // each node knows "next" node
string name; // and stores a value
Node(string initialName); // constructor for nodes
};

Node::Node(string initialName) {name = initialName; next = NULL;}

class MonkeyChain {
public:
MonkeyChain();
void threeKongs();
void printAll(); // not shown
void reverse();
private:
Node* helpReverse(Node* n); // reverse and return pointer to new start
Node* first;
};
\hide[
void MonkeyChain::printAll() {
// one possible approach: use a while loop
Node* current = first; // start at beginning

// if current isn't past the last node,
while (current != NULL) {
// print current node's name; then repeat loop w/next one
cout << current->name << endl;
current = current->next;
}
}
]\

MonkeyChain::MonkeyChain() {first = NULL;}

// a demo to create a length-3 list
void MonkeyChain::threeKongs() {
first = new Node("DK Sr.");
first->next = new Node("DK");
first->next->next = new Node("DK Jr.");
}

// private helper: reverse list trailing from n (n moves to end),
// return new front
Node* MonkeyChain::helpReverse(Node* n) {
\[
if (n == NULL) {
return NULL;
}
else if (n->next == NULL) {
return n; // nothing to reverse
}
else {
Node* tmp = helpReverse(n->next); // now n->next is at end
n->next->next = n; // move n past that end
n->next = NULL; // n is the end, fix its link
return tmp; // same new front
}
]\
}

void MonkeyChain::reverse() {
\[
first = helpReverse(first);
]\
}

int main() {
MonkeyChain mc;
mc.threeKongs();
mc.printAll(); cout << endl;
mc.reverse();
mc.printAll();
}

Java test suite
See manual

C++ test suite
json list of stdin/args tests
e.g. [{"stdin":"hi", "args":["4", "5"]}, {"stdin":"noargs"}]
to just run once with no input use [{}]

[
{}
]

C++ test suite
See manual

Forbidden substrings
json list of strings
e.g. ["for","while"]

["for", "while", "do"]
remove
Solution visibility remove
Java imports
json list of importables
e.g. ["java.util.*"]

remove
Override Java classname
else defaults to
websheet name
remove
Dependent on other websheets?
json list of websheet names in this folder
e.g. ["DataStructure"]

remove
Is example?
i.e., just a demo
remove
Add compiler flag(s)
json list of flags
e.g. ["-Wno-unused-variable"]

remove
Remove default compiler flag(s)
json list of flags
see default_cppflags
e.g. ["-Wno-write-strings"]

remove

Property	Value
Description html markup shown to student	Using recursion, create a method <tt>reverse()</tt> that reverses the elements in a linked list. You will need to declare and define a helper function.
Epilogue html markup shown when solved	remove
Public permissions	remove
Remarks Comments, history, license, etc.	remove
Engine
Choices json list of string, bool pairs e.g. `[["good", true], ["bad", false]]`
Correct answer
Template / Reference solution
Template / Reference solution	#include <iostream> #include <string> using namespace std; // structure of items in list struct Node { Node* next; // each node knows "next" node string name; // and stores a value Node(string initialName); // constructor for nodes }; Node::Node(string initialName) {name = initialName; next = NULL;} class MonkeyChain { public: MonkeyChain(); void threeKongs(); void printAll(); // not shown void reverse(); private: Node* helpReverse(Node* n); // reverse and return pointer to new start Node* first; }; \hide[ void MonkeyChain::printAll() { // one possible approach: use a while loop Node* current = first; // start at beginning // if current isn't past the last node, while (current != NULL) { // print current node's name; then repeat loop w/next one cout << current->name << endl; current = current->next; } } ]\ MonkeyChain::MonkeyChain() {first = NULL;} // a demo to create a length-3 list void MonkeyChain::threeKongs() { first = new Node("DK Sr."); first->next = new Node("DK"); first->next->next = new Node("DK Jr."); } // private helper: reverse list trailing from n (n moves to end), // return new front Node* MonkeyChain::helpReverse(Node* n) { \[ if (n == NULL) { return NULL; } else if (n->next == NULL) { return n; // nothing to reverse } else { Node* tmp = helpReverse(n->next); // now n->next is at end n->next->next = n; // move n past that end n->next = NULL; // n is the end, fix its link return tmp; // same new front } ]\ } void MonkeyChain::reverse() { \[ first = helpReverse(first); ]\ } int main() { MonkeyChain mc; mc.threeKongs(); mc.printAll(); cout << endl; mc.reverse(); mc.printAll(); }
Java test suite See manual
C++ test suite json list of stdin/args tests e.g. `[{"stdin":"hi", "args":["4", "5"]}, {"stdin":"noargs"}]` to just run once with no input use `[{}]`	[ {} ]
C++ test suite See manual
Forbidden substrings json list of strings e.g. `["for","while"]`	["for", "while", "do"] remove
Solution visibility	remove
Java imports json list of importables e.g. `["java.util.*"]`	remove
Override Java classname else defaults to websheet name	remove
Dependent on other websheets? json list of websheet names in this folder e.g. `["DataStructure"]`	remove
Is example? i.e., just a demo	remove
Add compiler flag(s) json list of flags e.g. `["-Wno-unused-variable"]`	remove
Remove default compiler flag(s) json list of flags see default_cppflags e.g. `["-Wno-write-strings"]`	remove

Optional properties:

Note: problems are open-source by default (see 'Public permissions'). Assumed license for open problems is Creative Commons 4.0 Attribution-ShareAlike unless specified in 'Remarks'.