单链表最大值节点算法：一趟遍历高效查找

单链表最大值节点算法：一趟遍历高效查找

本文介绍一种高效的算法，能够通过一趟遍历单链表，确定链表中值最大的节点。

算法步骤

1. 定义一个变量 max 用于存储最大值，初始化为链表的第一个结点的值。
2. 定义一个指针 p 指向链表的第一个结点。
3. 从链表的第二个结点开始遍历链表，每次比较当前结点的值和 max 的大小关系，如果当前结点的值比 max 大，则更新 max 的值。
4. 遍历完成后，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 为链表的长度。因为需要遍历整个链表一次。