C++递归完成单链表建立、输出和逆置

在C++中，递归可以用于创建、遍历以及逆置单链表。以下是递归实现的简单例子：

1. **创建单链表**：
递归创建链表通常涉及到将最后一个节点的指针指向新节点，并反复地添加元素。这里以构建数字序列为例：

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

ListNode* createList(int n, ListNode* head = nullptr) {
    if (n == 0) return head; // 遇到空，返回头节点
    return new ListNode(n, createList(n - 1, head)); // 递归调用，每次减少1
}

2. **输出单链表**：
递归遍历链表并打印值，直到遇到null：

void printList(ListNode* node) {
    if (node == nullptr) return; // 遍历结束
    cout << node->val << " "; // 输出节点值
    printList(node->next); // 递归处理下一个节点
}

3. **逆置单链表**：
递归可以应用于逆序操作，通过交换当前节点与其后续节点的位置，然后对剩余部分递归进行同样的操作。需要注意的是，需要临时保存当前节点的下一个节点：

ListNode* reverseList(ListNode* node, ListNode*& prev = nullptr) {
    if (node == nullptr || node->next == nullptr) {
        prev = node; // 如果到达尾部，prev就是新的头
        return nullptr;
    }
    ListNode* temp = node->next; // 保存当前节点的下一个
    node->next = prev; // 将当前节点接到前一个节点之后
    prev = node; // 更新前驱指针
    return reverseList(temp, prev); // 递归处理剩余部分
}