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

可以使用一个变量max记录当前最大值，从头节点开始遍历链表，每遇到一个节点就比较该节点的值和max的大小关系，如果该节点的值大于max，就更新max的值和最大节点的指针。最后遍历结束后，最大节点的指针即为所求。

具体实现如下：

Node* findMaxNode(Node* head, int n) {
    if (head == nullptr || n <= 0) {
        return nullptr;
    }
    Node* maxNode = head;
    int maxVal = head->val;
    Node* curr = head->next;
    for (int i = 2; i <= n; i++) {
        if (curr->val > maxVal) {
            maxNode = curr;
            maxVal = curr->val;
        }
        curr = curr->next;
    }
    return maxNode;
}

时间复杂度为O(n)，空间复杂度为O(1)。

相关问题

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

算法如下：

1. 声明一个变量max_value，用于存储当前已经遍历过的节点中的最大值。
2. 声明一个变量max_node，用于存储当前已经遍历过的节点中值最大的节点。
3. 从头节点开始，依次遍历单链表中的每个节点。
4. 对于每个节点，将节点的值和max_value进行比较。
5. 如果节点的值大于max_value，则更新max_value和max_node的值。
6. 遍历完成后，max_node即为长度为n的单链表中值最大的节点，返回该节点。

时间复杂度为O(n)，空间复杂度为O(1)。

设计一个算法,通过一趟遍历确定长度为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