设计一个算法判定单链表L的所有结点值是否是递增的
时间: 2024-11-12 18:37:31 浏览: 12
试设计实现在单链表中删去值相同的多余结点的算法。
设计一个算法来判断单链表 L 的所有节点值是否是递增的,可以采用迭代或者递归的方式。这里我给出一种简单的迭代方法:
1. 初始化两个指针 `prev` 和 `curr`,分别指向链表的头结点和第二个结点。
2. 遍历链表,每次比较当前结点的值 (`curr.val`) 与前一个结点的值 (`prev.val`):
a. 如果 `curr.val <= prev.val`,说明序列不是递增的,直接返回 `False`。
b. 更新 `prev` 指针为 `curr`,继续遍历下一个结点 (`prev = curr.next`)。
3. 当遍历到链表末尾时,如果没有发现违反递增的节点,说明整个链表是递增的,返回 `True`。
以下是伪代码表示:
```python
def is_increasing(head):
if head is None or head.next is None:
return True
prev = head.next
while prev is not None:
if prev.val < head.val:
return False
head = prev
prev = prev.next
return True
```
阅读全文