通过一趟遍历确定长度为n的单链表中值最大的节点
时间: 2023-05-14 08:07:10 浏览: 134
可以使用一个变量来记录当前遍历到的节点中的最大值,然后不断更新这个变量,直到遍历完整个链表。具体实现可以参考以下代码:
```
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的单链表中值最大节点
可以使用一个变量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)。