通过一趟遍历确定长度为n的单链表中值最大的节点

可以使用一个变量来记录当前遍历到的节点中的最大值，然后不断更新这个变量，直到遍历完整个链表。具体实现可以参考以下代码：

int findMax(ListNode* head) {
    int maxVal = INT_MIN;
    ListNode* cur = head;
    while (cur != nullptr) {
        maxVal = max(maxVal, cur->val);
        cur = cur->next;
    }
    return maxVal;
}

这段代码可以在O(n)的时间复杂度内完成遍历，并返回链表中的最大值。

相关问题

设计一个算法，通过一趟遍历确定长度n的单链表中值最大的结点

可以通过一趟遍历单链表来确定长度为n的链表中值最大的节点。具体算法如下：

1. 定义一个变量 `max_node`，初始化为链表的头结点。
2. 遍历链表，从头结点开始，依次比较每个节点的值与 `max_node` 的值。如果当前节点的值大于 `max_node` 的值，更新 `max_node` 为当前节点。
3. 遍历完成后，`max_node` 就是值最大的节点。

这个算法的时间复杂度为 O(n)，其中 n 是链表的长度。

设计一个算法,通过一趟遍历确定长度为n的单链表中值最大的节点

设计一个算法来找到长度为 n 的单链表中值最大的节点，可以采用迭代或递归的方式。这里我们提供一种简单的迭代方法：

1. 首先，创建两个指针，分别命名为 `maxNode` 和 `current`。初始时，将 `maxNode` 指向 NULL（表示没有发现最大值），`current` 指向链表的头节点。

2. 进入循环，当 `current` 不为空时，执行以下步骤：
a. 检查 `current` 节点的值是否大于 `maxNode` 的值。如果是，则更新 `maxNode` 为 `current`。
b. 移动 `current` 指针到下一个节点。

3. 循环结束后，`maxNode` 就指向了链表中值最大的节点。由于算法只遍历一次链表，所以时间复杂度是 O(n)。

以下是伪代码形式：

function findMaxNode(head):
    maxNode = null
    current = head

    while current is not null:
        if maxNode is null or current.value > maxNode.value:
            maxNode = current
        current = current.next

    return maxNode