Mixed review of lists

Questions 1 to 5 of 8

1. 1. In the length method for the intersection of two lists, why is the longer list moved forward before the two pointers are compared?

   Because the shared tail always starts at the head of the longer list.So both pointers have the same number of nodes left, which makes them reach the first shared node on the same step.So the shorter list's pointer reaches nullptr first, and the loop can stop.So the private nodes of the longer list are freed before the comparison.
2. 2. Why does swap_pairs_iterative start with a dummy node in front of the head?

   So the function can count the pairs before it swaps them.So the swap copies the values into the dummy node instead of relinking the nodes.So the first pair needs no special case, even though the head changes after the first swap.So the old head is freed before any pair is swapped.
3. 3. In reverse_one_group, the walk from group_prev runs off the end of the list. What does the function return, and what happens to the list?

   old_first, and the short block is reversed anyway.The dummy node, and the list is rotated by k.kth, and group_prev->next is set to nullptr.nullptr, and the list is not changed.
4. 4. What does this program print? ``cpp #include <iostream> struct Node { int value; Node* next = nullptr; }; 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 % n; 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; } int main() { Node* head = nullptr; for (int v = 6; v >= 1; --v) head = new Node{v, head}; head = rotate_right(head, 8); for (const Node* p = head; p != nullptr; p = p->next) { std::cout << p->value << (p->next ? " " : "\n"); } } ``

   3 4 5 6 1 25 6 1 2 3 46 1 2 3 4 51 2 3 4 5 6
5. 5. What does this program print? ``cpp #include <iostream> struct Node { int value; Node* next; }; Node* reverse_one_group(Node* group_prev, int k) { Node* kth = group_prev; for (int i = 0; i < k && kth != nullptr; ++i) kth = kth->next; if (kth == nullptr) return nullptr; Node* group_next = kth->next; Node* old_first = group_prev->next; Node* prev = group_next; Node* cur = old_first; while (cur != group_next) { Node* nxt = cur->next; cur->next = prev; prev = cur; cur = nxt; } group_prev->next = kth; return old_first; } Node* reverse_in_groups(Node* head, int k) { Node dummy{0, head}; Node* group_prev = &dummy; while (true) { Node* last = reverse_one_group(group_prev, k); if (last == nullptr) break; group_prev = last; } return dummy.next; } int main() { Node* head = nullptr; for (int v = 6; v >= 1; --v) head = new Node{v, head}; head = reverse_in_groups(head, 4); for (const Node* p = head; p != nullptr; p = p->next) { std::cout << p->value << (p->next ? " " : "\n"); } } ``

   1 2 3 4 5 64 3 2 1 6 54 3 2 1 5 63 4 1 2 5 6