2. 设计一个算法，判断一个单链表中各个结点值是否有序。

设计一个算法来判断单链表中节点值是否有序，可以采用迭代或递归的方式。这里给出一种迭代方法：

1. 首先，创建两个指针，`prev` 和 `current`，分别指向链表的头节点和第二个节点。

2. 进行遍历：
- 比较当前节点 `current` 的值与前一个节点 `prev` 的值。
- 如果当前节点的值小于等于前一个节点，说明链表可能是升序排列，继续检查下一个节点。
- 如果当前节点的值大于前一个节点，将 `prev` 更新为 `current`，然后移动到下一个节点 `current = current.next`。
- 当 `current` 走到链表尾部（即 `current == null`），则整个链表是有序的，返回 `true`。

3. 如果在整个遍历过程中发现有任意一次节点值违反了递增顺序，说明链表是无序的，返回 `false`。

以下是伪代码表示：

def is_sorted_list(head):
    prev = None if head is None else head.val
    current = head.next

    while current is not None:
        if current.val < prev:
            return False
        prev = current.val
        current = current.next

    return True

相关问题

设计一个算法,判断一个单链表中各个结点值是否有序

设计一个算法来判断一个单链表中各个节点的值是否有序，通常可以使用比较节点的方式来进行。这里提供一种简单的线性遍历算法：

1. 首先，我们需要两个指针，一个指向当前节点（`current`），另一个指向前一个节点（`previous`）。初始化它们为链表的头节点和`null`。

2. 进入循环，直到`current`为空（即链表结束）：
a. 检查`current`的值是否小于等于`previous`的值。如果大于，则说明链表未按升序排列，返回`false`。
b. 更新`previous`为`current`，然后移动到下一个节点，即`current = current.next`。

3. 如果整个链表都遍历完了，且没有发现违反升序的情况，那么链表就是有序的，返回`true`。

Python伪代码示例:

def is_sorted_linked_list(head):
    if not head or not head.next:
        return True

    previous = None
    current = head
    while current:
        if (previous and current.val > previous.val):
            return False
        previous = current
        current = current.next

    return True

设计一个算法，判断一个单链表中各个结点值是否有序

设计一个算法来判断一个单链表中各节点的值是否有序，通常有两种情况需要考虑：升序和降序。这里我们假设是升序排序。

1. **升序判断** (递归法)：
- 如果链表为空或只有一个元素，则它是有序的。
- 从第二个节点开始，如果当前节点的值大于前一个节点的值，那么链表不是升序的，返回 false。
- 如果遍历完整个链表都没有发现违反顺序的情况，说明链表是升序的，返回 true。

def is_sorted(head):
    if not head or not head.next:
        return True
    if head.next.value < head.value:
        return False
    return is_sorted(head.next)

2. **非递归法** (迭代法)：
- 定义两个指针，一个（slow）每次移动一步，另一个（fast）每次移动两步。
- 当fast指针到达链表末尾时，如果slow指针还在遍历，说明链表已经有序；若fast和slow位置交换了，说明链表未有序。

def is_sorted_iterative(head):
    slow = fast = head
    while fast and fast.next:
        if fast.value > slow.value:
            return False
        slow = slow.next
        fast = fast.next.next
    return True