这道题要求设计一个算法,通过一趟遍历确定链表中值最大的节点,然后返回该节点的数据域。
时间: 2023-12-25 16:04:48 浏览: 81
递归链表中值最大的节点
4星 · 用户满意度95%
这个问题可以使用一个变量 `maxNode` 记录当前遍历到的值最大的节点,初始值为链表的头节点。然后依次遍历链表的每个节点,如果当前节点的值大于 `maxNode` 的值,则更新 `maxNode` 为当前节点。最后返回 `maxNode` 的值即可。
以下是这个算法的具体实现:
```
int findMax(ListNode* head) {
if (head == nullptr) {
return -1; // 链表为空,返回一个无效值
}
ListNode* maxNode = head;
ListNode* curr = head;
while (curr != nullptr) {
if (curr->val > maxNode->val) {
maxNode = curr;
}
curr = curr->next;
}
return maxNode->val;
}
```
这个算法的时间复杂度为O(n),空间复杂度为O(1)。
阅读全文