面试题：C++递归函数中指针与动态内存管理

Question

假设你有一个链表结构，节点定义如下：struct ListNode { int val; ListNode* next; }; 编写一个递归函数，该函数接收链表头指针，对链表节点的val值进行平方操作，并在递归过程中处理好指针的移动和内存释放（如果需要）。注意，在递归调用中正确处理指针以确保链表结构的完整性。

Answer 1

#include <iostream>

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* squareListRecursive(ListNode* head) {
    if (head == nullptr) {
        return nullptr;
    }
    head->val = head->val * head->val;
    head->next = squareListRecursive(head->next);
    return head;
}

void printList(ListNode* head) {
    while (head != nullptr) {
        std::cout << head->val << " -> ";
        head = head->next;
    }
    std::cout << "nullptr" << std::endl;
}

void deleteList(ListNode* head) {
    while (head != nullptr) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }
}

你可以使用以下方式调用：

int main() {
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);

    std::cout << "Original list: ";
    printList(head);

    head = squareListRecursive(head);

    std::cout << "List after squaring: ";
    printList(head);

    deleteList(head);

    return 0;
}

上述代码中，squareListRecursive函数通过递归方式对链表节点的val值进行平方操作。在递归过程中，首先对当前节点的val值进行平方，然后递归处理下一个节点，并将处理后的下一个节点指针重新赋值给当前节点的next指针，确保链表结构的完整性。

printList函数用于打印链表，deleteList函数用于释放链表所占用的内存。在main函数中，创建一个简单链表，调用squareListRecursive函数对链表节点值进行平方操作并打印结果，最后释放链表内存。