单链表操作练习。 设计一个算法,通过一趟遍历确定长度为n的单链表中值最大的结点。
时间: 2024-09-22 08:08:12 浏览: 49
单链表操作练习中,设计这样的算法通常需要考虑一边遍历链表,一边保存最大值的过程。以下是一个简单的Python示例:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def find_largest_node(head: ListNode, n: int) -> ListNode:
if not head or (head and n <= 0): # 如果链表为空或元素不足
return None
current = head
largest_val = float('-inf') # 初始化最大值为负无穷大
count = 0 # 记录已访问节点的数量
while current and count < n:
if current.val > largest_val: # 更新最大值
largest_val = current.val
current = current.next
count += 1
return largest_val != float('-inf') # 如果找到最大值则返回,否则返回None
# 使用示例
# 假设链表节点结构如下:
# head = ListNode(1)
# head.next = ListNode(3)
# head.next.next = ListNode(5)
# head.next.next.next = ListNode(9)
# 调用函数 find_largest_node(head, 4),结果应为ListNode(9)
```
这个算法遍历链表一次,只检查前n个节点,如果找到了第n个节点并且其值大于当前的最大值,就更新最大值。如果n超过链表长度,则返回最后一个节点的值。
阅读全文