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

1. 求链表中的最大整数

int maxNum(ListNode* head) {
if(head == nullptr) { // 链表为空，返回INT_MIN
return INT_MIN;
}
int maxVal = maxNum(head->next); // 递归求解子问题
return max(head->val, maxVal); // 返回当前节点值和子问题解的最大值
}

2. 求所有整数的平均值

double average(ListNode* head, int count = 0, int sum = 0) {
if(head == nullptr) { // 链表遍历完成，返回平均值
return (double)sum / count;
}
return average(head->next, count + 1, sum + head->val); // 递归求解子问题，并累加count和sum
}

相关问题

已知f为单链表的表头指针，链表中存储的都是整型数据，试写出实现下列运算的递归算法

要实现单链表的递归操作，比如求和、查找特定值等，首先我们需要定义递归的基本情况和递归调用步骤。这里假设我们有一个简单的单链表结构：

// 单链表节点结构
typedef struct ListNode {
    int val;         // 节点值
    ListNode* next;   // 指向下一个节点的指针
} ListNode;

对于递归函数，我们可以考虑以下几个常见的递归操作：

1. **递归求和 (Sum)**:
- 基本情况：如果链表为空，则返回0。
- 递归情况：对非空链表的头部节点计算其值加上其后继节点值的和。

int sum(ListNode* head) {
    if (head == nullptr) {     // 链表为空，返回0
        return 0;
    } else {
        return head->val + sum(head->next);   // 递归调用
    }
}

2. **查找特定值 (Find)**:
- 基本情况：如果找到目标值，返回当前节点；若遍历到末尾未找到，返回nullptr。
- 递归情况：检查当前节点是否等于目标值，如果不是则继续向下遍历。

ListNode* find(ListNode* head, int target) {
    if (head == nullptr || head->val == target) {   // 找到或结束条件
        return head;
    } else {
        return find(head->next, target);   // 递归调用
    }
}

3. **删除所有等于目标值的节点 (Delete)**
- 基本情况：如果链表为空或节点值不等于目标，直接返回。
- 递归情况：处理当前节点，然后递归处理后继节点。

void deleteNodes(ListNode** head, int target) {
    if (*head != nullptr && (*head)->val == target) {
        ListNode* temp = *head;
        *head = (*head)->next;
        delete temp;
    } else if (*head != nullptr) {
        deleteNodes(&(*head)->next, target);
    }
}

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

在C++中，我们可以使用递归和迭代的方式分别实现链表的最大整数和平均值计算。

**递归算法**:

1. **求最大整数（递归）**:
- 如果链表为空，返回INT_MIN作为初始情况；
- 否则，比较当前节点的值和下一个节点的最大值，取较大者为结果，并继续递归到链表尾部。

   int maxRecursive(Node* f, int maxSoFar = INT_MIN) {
       if (f == nullptr)
           return maxSoFar;
       else
           return max(maxSoFar, f->val > maxSoFar ? f->val : maxRecursive(f->next));
   }

2. **求平均值（递归）**:
- 首先需要计算链表的总和，然后除以节点总数（包括头节点）。可以辅助一个变量记录总和和节点计数；
- 初始情况，如果链表为空，总和为0，节点数为0；
- 否则，累加当前节点值并增加计数，然后递归处理下一个节点。

   double averageRecursive(Node* f, int sum = 0, int count = 1) {
       if (f == nullptr)
           return 0.0;
       else {
           sum += f->val;
           count++;
           return averageRecursive(f->next, sum, count);
       }
   }
   double getAverageRecursive(Node* f) {
       int totalSum = sumRecursive(f);
       int totalNodes = countRecursive(f);
       return static_cast<double>(totalSum) / totalNodes;
   }

**非递归算法**:

1. **求最大整数（非递归）**:
- 使用栈保存遍历过程中的最大值，从头节点开始，逐个比较更新最大值。

   Node* findMaxIterative(Node* f) {
       if (f == nullptr)
           return nullptr;
       Node* maxNode = f;
       while (f->next != nullptr) {
           if (f->val > maxNode->val)
               maxNode = f;
           f = f->next;
       }
       return maxNode;
   }

2. **求平均值（非递归）**:
- 初始化总和、计数，遍历整个链表。

   double averageNonRecursive(Node* f) {
       int sum = 0;
       int count = 0;
       for (; f != nullptr; f = f->next) {
           sum += f->val;
           count++;
       }
       return static_cast<double>(sum) / count;
   }