Palindrome and partition

Questions 1 to 5 of 7

1. 1. Why does isPalindrome put the second half back in its original order (step 4) even when it has already found a mismatch?

   A mismatch means the second half must be reversed again so the comparison can be repeatedThe reverse frees the nodes of the second half, so they must be restored firstThe caller still needs the list in its original order, and returning early would leave the second half reversedA mismatch changes the values in the list, so the list must be restored
2. 2. In split_by, why is yes_tail a plain Node* and not a NodePtr?

   A plain pointer does not own the node, so the tail can never free a node. The chain owns itA unique_ptr cannot point at the last node of a chainA unique_ptr is too slow to move once per nodeThe yes_tail pointer must be nullptr at the start of the loop
3. 3. What does this program print? ``cpp #include <iostream> struct Node { int value; Node* next = nullptr; }; Node* reverse(Node* head) { Node* prev = nullptr; while (head != nullptr) { Node* next = head->next; head->next = prev; prev = head; head = next; } return prev; } int main() { Node n6{7}; Node n5{4, &n6}; Node n4{9, &n5}; Node n3{9, &n4}; Node n2{4, &n3}; Node n1{7, &n2}; Node* slow = &n1; Node* fast = &n1; while (fast->next != nullptr && fast->next->next != nullptr) { slow = slow->next; fast = fast->next->next; } Node* second = reverse(slow->next); std::cout << "slow " << slow->value << ", reversed second half starts " << second->value << '\n'; return 0; } ``

   slow 4, reversed second half starts 9slow 9, reversed second half starts 9slow 9, reversed second half starts 7slow 7, reversed second half starts 7
4. 4. What does this program print? ``cpp #include <iostream> #include <vector> int main() { std::size_t position = 0; auto goesToOdd = [&position](int) { return position++ % 2 == 0; }; std::vector<int> odd; std::vector<int> even; for (int v : {10, 20, 30, 40, 50}) { if (goesToOdd(v)) { odd.push_back(v); } else { even.push_back(v); } } std::cout << odd.size() << " odd positions, " << even.size() << " even positions, last odd-position value " << odd.back() << '\n'; return 0; } ``

   2 odd positions, 3 even positions, last odd-position value 403 odd positions, 2 even positions, last odd-position value 503 odd positions, 2 even positions, last odd-position value 302 odd positions, 3 even positions, last odd-position value 50
5. 5. Put these steps in the order that isPalindrome runs them.

   Use the arrows to put the steps in order.

   1. 1.Reverse the second half, starting at slow->next↑↓
   2. 2.Reverse the second half again and attach it to slow, whatever the answer↑↓
   3. 3.Walk the front half and the reversed second half together, comparing values↑↓
   4. 4.Move slow one node and fast two nodes until fast reaches the end, so slow stops on the middle↑↓