设计一个算法，通过一趟遍历确定长度为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的单链表中值最大的结点

可以通过一趟遍历单链表来确定长度为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