算法设计题：已知f为单链表的表头指针，链表中存储整型数据，试写出求所有整数平均值的算法。 (1)给出算法的基本思想。 (2)写出算法，并对算法中的关键步骤适当注释。 (3)给出算法的时间和空间复杂度。

(1) 算法的基本思想是遍历链表，统计链表中所有整数的和，再除以链表中整数的个数即可得到平均值。

(2) 算法如下：

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

double getAverage(ListNode* f) {
    int sum = 0; // 初始化链表中所有整数的和为0
    int count = 0; // 初始化链表中整数的个数为0
    ListNode* p = f; // 从链表头部开始遍历
    while (p != NULL) {
        sum += p->val; // 统计整数的和
        count++; // 统计整数的个数
        p = p->next; // 移动到下一个节点
    }
    return (double)sum / count; // 计算平均值
}

(3) 时间复杂度为O(n)，其中n为链表中整数的个数。空间复杂度为O(1)，不需要额外的空间。

相关问题

已知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;
}

已知f为单链表的表头指针, 链表中存储的都是整型数据，试写出实现下列运算的递归算法： ① 求链表中的最大整数； ② 求链表的结点个数； ③ 求所有整数的平均值。

好的，我明白了。以下是你要求的递归算法：

① 求链表中的最大整数：

int getMax(ListNode* head) {
    if (head == NULL) {
        return INT_MIN;
    }
    int currMax = head->val;
    int restMax = getMax(head->next);
    return max(currMax, restMax);
}

② 求链表的结点个数：

int getCount(ListNode* head) {
    if (head == NULL) {
        return 0;
    }
    return 1 + getCount(head->next);
}

③ 求所有整数的平均值：

double getAverage(ListNode* head, int sum, int count) {
    if (head == NULL) {
        return (double)sum / count;
    }
    sum += head->val;
    count++;
    return getAverage(head->next, sum, count);
}

请注意，以上算法是基于单链表的。如果你的链表不是单链表，或是存储其他类型的数据（不是整型），上述算法需要做相应的修改。