设单链表具有头结点，且表长大于0。试设计一个算法，通过一趟遍历返回单链表中结点数据 域最大值 (int 型数据）。函数声明如下，并加入简要的注释或说明

int maxElem(Node* head);

算法思路：

1. 首先定义一个最大值变量 `max`，初始值为头结点后面第一个结点的数据域值。
2. 从头结点开始遍历单链表，依次比较每个结点的数据域值与 `max` 的大小关系，如果当前结点的数据域值大于 `max`，则更新 `max` 的值。
3. 遍历结束后，返回 `max` 的值即可。

算法实现：

int maxElem(Node* head) {
    int max = head->next->data;  // 初始化最大值为第一个结点的数据域值
    Node* p = head->next;  // 从第一个结点开始遍历
    while (p != nullptr) {
        if (p->data > max) {
            max = p->data;  // 更新最大值
        }
        p = p->next;  // 移动到下一个结点
    }
    return max;
}

相关问题

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

可以使用一个变量来记录当前最大值的结点，然后遍历整个单链表，如果当前结点的值比记录的最大值还大，就更新最大值结点的指针。最后遍历完成后，最大值结点就是整个单链表中值最大的结点。以下是示例代码：

Node* findMaxNode(Node* head) {
    if (head == nullptr) {
        return nullptr;
    }
    Node* maxNode = head;
    Node* curNode = head->next;
    while (curNode != nullptr) {
        if (curNode->value > maxNode->value) {
            maxNode = curNode;
        }
        curNode = curNode->next;
    }
    return maxNode;
}

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

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

### 回答1：
可以使用一个变量来记录当前最大值，然后遍历整个链表，如果当前结点的值比最大值大，则更新最大值和最大值所在的结点。最后返回最大值所在的结点即可。

以下是示例代码：

ListNode* findMaxNode(ListNode* head) {
    if (!head) return nullptr;
    ListNode* maxNode = head;
    int maxValue = head->val;
    while (head) {
        if (head->val > maxValue) {
            maxValue = head->val;
            maxNode = head;
        }
        head = head->next;
    }
    return maxNode;
}

注意：这里假设链表中的结点值都是正整数，如果存在负数，需要在初始化最大值时设置为 INT_MIN。

### 回答2：
设计一个算法，通过一趟遍历在单链表中确定值最大的节点可以按照以下步骤进行：

1. 定义一个指针maxNode，指向当前最大值所在的节点，初始化为链表的第一个节点。

2. 定义一个变量maxValue，表示当前最大值，初始化为链表第一个节点的值。

3. 从链表的第二个节点开始遍历：

- 比较当前节点的值与maxValue的大小，如果大于maxValue，则更新maxValue的值为当前节点的值，并将maxNode指向当前节点。

- 如果当前节点的值不大于maxValue，则继续遍历下一个节点。

4. 遍历结束后，maxNode所指向的节点即为值最大的节点。

例如，假设链表的节点依次为1->3->5->2->4，根据上述算法：

- 初始时，maxNode指向节点1，maxValue的值为1。

- 遍历到节点3时，值为3大于maxValue的值1，所以更新maxValue的值为3，将maxNode指向节点3。

- 遍历到节点5时，值为5大于maxValue的值3，所以更新maxValue的值为5，将maxNode指向节点5。

- 遍历到节点2时，值为2不大于maxValue的值5，所以继续遍历下一个节点。

- 遍历到节点4时，值为4不大于maxValue的值5，所以继续遍历下一个节点。

最终，maxNode指向的节点为值最大的节点，即节点5。

### 回答3：
设计一个算法可以通过一次遍历在单链表中确定值最大的节点。算法如下：

1. 创建一个指针变量`maxNode`用于保存当前找到的值最大的节点，初始值为链表的第一个节点。
2. 创建一个指针变量`current`用于遍历整个链表，初始值为链表的第一个节点。
3. 从链表的第二个节点开始，依次遍历链表中的每个节点，直到遍历到链表的最后一个节点为止。
4. 在遍历的过程中，判断当前节点的值是否大于`maxNode`节点的值。
5. 如果是，则更新`maxNode`节点为当前节点。
6. 继续遍历下一个节点。
7. 当遍历完整个链表之后，`maxNode`节点即为值最大的节点。

该算法仅需要一趟遍历，将链表中的每个节点都与`maxNode`节点的值进行比较，如果当前节点的值大于`maxNode`节点的值，则更新`maxNode`节点为当前节点，最终找到值最大的节点。由于只进行一次遍历，所以时间复杂度为O(n)，其中n为链表的节点数。