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

### 回答1：
题目要求实现下列运算法则：

（1）求链表中的最大整数。

（2）求所有整数的平均值。

由于链表的头指针已知，直接遍历整个链表求解即可：

（1）遍历链表，用一个变量max记录当前找到的最大整数。每找到一个节点，就将它的值与max比较，若大于max则更新max的值。最终max的值即为所求最大整数。

（2）遍历链表，用两个变量sum和cnt记录当前所有整数的和以及节点个数。每找到一个节点，就累加它的值到sum中，并将cnt加1。最终求解平均值就是sum/cnt。

代码示例：

# 定义链表节点类
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    # 求最大整数
    def max_val(self, head: ListNode) -> int:
        max_val = head.val
        cur = head.next
        while cur:
            if cur.val > max_val:
                max_val = cur.val
            cur = cur.next
        return max_val

    # 求平均值
    def avg_val(self, head: ListNode) -> float:
        sum_val = 0
        cnt = 0
        cur = head
        while cur:
            sum_val += cur.val
            cnt += 1
            cur = cur.next
        return sum_val / cnt

### 回答2：
1. 求链表中的最大整数

（1）递归算法

思路：将链表分为两部分，一部分为链表的头节点，另一部分为头节点之后的所有节点。然后分别求出两部分的最大值，比较两部分的最大值，返回较大的值。

代码：

int max(Node* f) {
    if (f == NULL) {
        return INT_MIN; // 如果链表为空，则返回最小整数值
    } else {
        int head_value = f->data;
        int rest_value = max(f->next); // 递归调用
        return head_value > rest_value ? head_value : rest_value;
    }
}

（2）非递归算法

思路：利用循环遍历链表，比较每个节点的值与当前最大值的大小，将较大的值作为当前最大值。

代码：

int max(Node* f) {
    int max_value = INT_MIN;
    while (f != NULL) {
        if (f->data > max_value) {
            max_value = f->data;
        }
        f = f->next;
    }
    return max_value;
}

2. 求所有整数的平均值

（1）递归算法

思路：将链表分为两部分，一部分为链表的头节点，另一部分为头节点之后的所有节点。然后分别求出两部分的节点个数和节点值的和，相加得到整个链表节点个数和节点值的和，并将其返回。最后计算平均值并返回结果。

代码：

float avg(Node* f) {
    if (f == NULL) {
        return 0; // 如果链表为空，则平均值为0
    } else {
        int head_value = f->data;
        int rest_length = length(f->next); // 递归调用
        int rest_sum = sum(f->next);
        return (head_value + rest_sum) / (float)(1 + rest_length);
    }
}

（2）非递归算法

思路：利用循环遍历链表，累加节点值的和并记录节点个数，最后计算平均值并返回结果。

代码：

float avg(Node* f) {
    int count = 0;
    int sum = 0;
    while (f != NULL) {
        count++;
        sum += f->data;
        f = f->next;
    }
    return sum / (float)count;
}

### 回答3：
递归算法实现链表最大整数和平均值：

1. 求链表最大整数

实现方法：

a. 如果链表为空，返回 INT_MIN（整型数据类型的最小值）

b. 如果链表非空，求出链表中后面的最大值

c. 返回比较 head->data 和后面的最大值，得出最大值

代码如下：

int getMax(ListNode* head) {
    if (head == NULL) {
        return INT_MIN;
    }
    int max = getMax(head->next);
    return head->data > max ? head->data : max;
}

2. 求链表所有整数平均数

实现方法：

a. 如果链表为空，返回 0

b. 如果链表非空，求出链表中后面的整数和和结点数量

c. 返回当前结点的值加上后面的所有整数和，除以总结点数量

代码如下：

double getAvg(ListNode* head, int size) {
    if (head == NULL) {
        return 0;
    }
    double sum = getAvg(head->next, size + 1) * size + head->data;
    return sum / (size + 1);
}

非递归算法实现链表最大整数和平均值：

1. 求链表最大整数

实现方法：

a. 如果链表为空，返回 INT_MIN

b. 定义一个变量 max 来存储当前链表的最大值，设初值为 INT_MIN

c. 遍历链表，如果当前结点的值比 max 大，则更新 max

d. 返回 max

代码如下：

int getMax2(ListNode* head) {
    if (head == NULL) {
        return INT_MIN;
    }
    int max = INT_MIN;
    while (head != NULL) {
        if (head->data > max) {
            max = head->data;
        }
        head = head->next;
    }
    return max;
}

2. 求链表所有整数平均数

实现方法：

a. 如果链表为空，返回 0

b. 定义一个变量 size，用来存储链表的长度

c. 定义一个变量 sum，用来存储链表所有整数的和

d. 遍历链表，将当前结点的值加到 sum 中，size 加 1

e. 返回 sum 除以 size

代码如下：

double getAvg2(ListNode* head) {
    if (head == NULL) {
        return 0;
    }
    int size = 0;
    double sum = 0;
    while (head != NULL) {
        sum += head->data;
        size++;
        head = head->next;
    }
    return sum / size;
}