（必做题）已知f为单链表的表头指针，链表中存储的都是整型数据，试写出实现下列运算的递归算法：（1)求链表中的最大整数。（2)求所有整数的平均值。算法题C++

在C++中，我们可以编写递归算法来处理单链表并求解最大整数和平均值。这里给出基本的递归思路：

// 定义链表节点结构体
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 递归求最大值
int findMax(ListNode* f) {
    // 基线条件：空链表或只有一个元素
    if (f == nullptr || f->next == nullptr) {
        return f ? f->val : INT_MIN;  // 如果链表非空，返回第一个元素；否则返回INT_MIN作为初始的最大值
    }
    
    // 递归条件：比较当前元素与下一个元素的最大值
    return std::max(f->val, findMax(f->next));
}

// 递归求平均值（需要遍历整个链表）
double calculateAverage(ListNode* f) {
    // 基线条件：空链表
    if (f == nullptr) {
        return 0.0;
    }
    
    // 递归过程：累加当前元素并移动到下一个节点，同时记录元素数量
    double sum = f->val;
    int count = 1;
    if (f->next != nullptr) {
        sum += calculateAverage(f->next);
        count += 1;
    }
    
    // 返回平均值
    return sum / count;
}