Digit lists and pair swaps

Questions 1 to 5 of 8

1. 1. What does this program print? ``cpp #include <iostream> struct Node { int value; Node* next; }; Node* swap_pairs_recursive(Node* head) { if (head == nullptr || head->next == nullptr) return head; Node* second = head->next; head->next = swap_pairs_recursive(second->next); second->next = head; return second; } int main() { Node n5{5, nullptr}, n4{4, &n5}, n3{3, &n4}, n2{2, &n3}, n1{1, &n2}; Node* head = swap_pairs_recursive(&n1); for (Node* p = head; p != nullptr; p = p->next) { std::cout << p->value << ' '; } std::cout << '\n'; } ``

   1 2 3 4 52 1 4 3 52 1 3 4 55 4 3 2 1
2. 2. What does this program print? ``cpp #include <iostream> int main() { for (int total : {14, 25, 19}) { std::cout << "write " << total % 10 << ", carry " << total / 10 << '\n'; } } ``

   write 14, carry 0; write 25, carry 0; write 19, carry 1write 4, carry 2; write 5, carry 2; write 9, carry 1write 4, carry 1; write 5, carry 2; write 9, carry 1write 4, carry 1; write 5, carry 2; write 0, carry 1
3. 3. What does this program print? ``cpp #include <iostream> #include <string> #include <string_view> struct Node { int digit; Node* next; explicit Node(int d) : digit(d), next(nullptr) {} }; Node* from_text(std::string_view text) { Node dummy(0); Node* tail = &dummy; for (auto it = text.rbegin(); it != text.rend(); ++it) { tail->next = new Node(*it - '0'); tail = tail->next; } return dummy.next; } std::string list_text(const Node* head) { std::string out; for (const Node* p = head; p != nullptr; p = p->next) { if (!out.empty()) out += " -> "; out += std::to_string(p->digit); } return out; } int main() { std::cout << list_text(from_text("250")) << '\n'; } ``

   0 -> 5 -> 22 -> 5 -> 02 -> 0 -> 5250
4. 4. This rotate_right should rotate the list right by k. It is called on 1 -> 2 -> 3 -> 4 -> 5 with k set to 7, and it returns 2 -> 3 -> 4 -> 5 -> 1, which is wrong. Which line is the bug? ``cpp Node* rotate_right(Node* head, int k) { if (head == nullptr || head->next == nullptr) return head; int n = 1; Node* tail = head; while (tail->next != nullptr) { tail = tail->next; ++n; } int shift = k; if (shift == 0) return head; tail->next = head; int steps = n - shift - 1; Node* new_tail = head; for (int i = 0; i < steps; ++i) { new_tail = new_tail->next; } Node* new_head = new_tail->next; new_tail->next = nullptr; return new_head; } ``

   tail->next = head;, which closes the ring too earlynew_tail->next = nullptr;, which must come before the new head is savedif (shift == 0) return head;, which returns too early for k of 7int shift = k;, which skips the k % n step, so steps becomes negative
5. 5. This version of swap_pairs_iterative changes the order of the four pointer steps. It is called on 1 -> 2 -> 3 -> 4. What happens? ``cpp Node* swap_pairs_iterative(Node* head) { Node dummy(0); dummy.next = head; Node* prev = &dummy; while (prev->next != nullptr && prev->next->next != nullptr) { Node* first = prev->next; Node* second = first->next; second->next = first; first->next = second->next; prev->next = second; prev = first; } return dummy.next; } ``

   The result is 2 -> 1 -> 4 -> 3, the same as the correct versionNodes 3 and 4 are dropped, so the result is 2 -> 1Node 1 ends up pointing at itself, so the loop never finishesThe function returns nullptr, because the dummy node is lost