设计一个算法,通过一趟遍历在单链表中确定值最大的结点。
算法步骤:
- 定义一个变量max用于存储最大值,初始化为链表的第一个结点的值。
- 定义一个指针p指向链表的第一个结点。
- 从链表的第二个结点开始遍历链表,每次比较当前结点的值和max的大小关系,如果当前结点的值比max大,则更新max的值。
- 遍历完成后,max就是链表中值最大的结点的值。
算法实现:
def find_max(head):
if head is None:
return None
max_val = head.val
p = head.next
while p is not None:
if p.val > max_val:
max_val = p.val
p = p.next
return max_val
时间复杂度:O(n),其中n为链表的长度。因为需要遍历整个链表一次。
原文地址: https://www.cveoy.top/t/topic/zwM 著作权归作者所有。请勿转载和采集!