已知 f 为单链表的表头指针, 链表中存储的都是整型数据,试写出实现下列运算的递归 算法:① 求链表中的最大整数;② 求链表的结点个数;③ 求所有整数的平均值。
时间: 2025-06-22 08:47:37 浏览: 13
对于单链表,由于递归操作通常涉及到从当前节点向下遍历直到找到结束节点,这里我会给出每个操作的递归算法:
1. **求链表中的最大整数**:
```python
def find_max(head):
# 基线条件:如果链表为空,返回None表示没有元素
if head is None or head.next is None:
return None
# 递归条件:比较当前节点的值与子链表的最大值
max_val = max(head.val, find_max(head.next))
return max_val
```
2. **求链表的结点个数**:
```python
def count_nodes(head):
# 基线条件:如果链表为空,返回0
if head is None:
return 0
# 递归条件:增加当前节点计数并加上子链表的节点数
return 1 + count_nodes(head.next)
```
3. **求所有整数的平均值**:
```python
from typing import Optional
def average_linked_list(head: Optional[int]) -> float:
def sum_and_count(node: Optional[int], total: int, count: int) -> tuple[int, int]:
# 如果节点为空,更新总和和计数
if node is None:
return total, count
else:
total += node.value
count += 1
# 继续递归到下一个节点
return sum_and_count(node.next, total, count)
_, n = sum_and_count(head, 0, 0) # 获取总和和节点总数
return total / n if n > 0 else None # 返回平均值(避免除以零错误)
```
阅读全文
相关推荐

















