设计算法判断非空单链表是否递增有序。
时间: 2024-11-06 14:19:55 浏览: 23
判断非空单链表是否递增有序可以通过遍历链表的方式来进行。以下是算法的基本步骤:
1. 定义两个指针 `current` 和 `previous`,初始时都指向链表的头节点 `head`,`previous` 设置为 `NULL`。
2. 开始循环,只要 `current` 节点不为空:
a. 检查 `current` 的值是否大于 `previous` 的值。如果小于等于,说明链表不是递增有序,直接返回 `false`。
b. 更新 `previous` 为 `current`,因为我们需要用 `current` 的前一个节点值进行比较。
c. 移动 `current` 到下个节点,即 `current = current->next`。
3. 如果整个链表都遍历完了,且每个节点的值都满足递增条件,那么链表就是递增有序的,返回 `true`。
以下是一个伪代码形式的示例:
```cpp
bool isMonotonicIncreasing(ListNode* head) {
ListNode *previous = nullptr;
ListNode *current = head;
while (current != nullptr) {
if (previous != nullptr && current->val <= previous->val) {
return false;
}
previous = current;
current = current->next;
}
return true;
}
```
阅读全文