判断给定的单链表L是否为有序(非递增或非递减),将对应的函数命名为ListOrder_L()。新手小白写
时间: 2024-10-20 18:15:08 浏览: 16
判断一个单链表是否有序,可以创建一个辅助节点,遍历链表的同时比较当前节点的值与辅助节点的值。如果链表是非递增排序,那么每个节点的值应该小于等于前一个节点的值;如果是非递减排序,则每个节点的值应该大于等于前一个节点的值。
以下是使用Python语言实现的简单示例:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def ListOrder_L(L: ListNode) -> bool:
if L is None or L.next is None:
return True # 空链表或只有一个元素的链表都是有序的
prev_val = L.val
while L is not None:
if (L.val < prev_val and list_order == 'non-decreasing') or \
(L.val > prev_val and list_order == 'non-increasing'):
return False # 发现值不符合顺序,返回False
prev_val = L.val
L = L.next
return True # 如果能遍历完整个链表而未发现违反顺序的情况,说明链表是有序的
# 使用示例:
list_order = 'non-increasing' # 或者 'non-decreasing'
head = ListNode(5, ListNode(4, ListNode(3, ListNode(2, ListNode(1)))))
print(ListOrder_L(head)) # 输出:True
```
这个`ListOrder_L()`函数首先检查链表长度,然后通过迭代检查每个节点的值是否符合顺序要求。当找到不符合顺序的节点时,立即返回`False`;如果遍历完所有节点都没有发现异常,返回`True`表示链表是有序的。
阅读全文