三、算法设计(共40分) 判断单链表是否递增有序(12分)。

在计算机科学中，判断单链表是否递增有序是一个常见的基础题目。给定一个单向链表，你需要检查其中的节点值是否按照升序排列。这里有一个简单的算法设计：

1. 创建两个指针，初始时都指向链表的头节点。
2. 进行遍历，比较当前节点的值与前一个节点的值。
a. 如果当前节点值小于前一个节点值，则链表不是递增有序的，返回`false`。
b. 每次移动到下一个节点，将前一个节点更新为当前节点。
3. 遍历完成后，如果没有发现违反递增排序的情况，说明链表是递增有序的，返回`true`。

以下是伪代码示例：

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

    current = head.next
    while current:
        if current.val < head.val:
            return False
        head = current
        current = current.next

    return True

相关问题

算法设计判断单链表是否递增有序

算法设计判断单链表是否递增有序通常涉及遍历链表并比较相邻节点的值。以下是简单的步骤：

1. 创建一个指针，初始化为链表的头节点。
2. 遍历链表，如果当前节点不是第一个节点，就需要检查它是否大于前一个节点。如果当前节点的值小于等于前一个节点的值，那么链表就不是递增排序的。
- 使用`if (currentNode->data <= previousNode->data)`这个条件进行比较。
- 如果找到不符合递增顺序的情况，立即返回`false`。
3. 每次移动到下一个节点，更新`previousNode`为`currentNode`，继续下一次迭代。
4. 当遍历完整个链表而未发现违反递增顺序的节点时，说明链表是递增有序的，此时返回`true`。

这里的关键在于使用两个指针来跟踪当前节点和前一个节点，并在遍历时做比较。以下是伪代码示例：

def isMonotonic(head):
    if head is None or head.next is None:
        return True

    previous = head
    current = head.next

    while current is not None:
        if current.data < previous.data:
            if previous.data <= current.data:
                # 从第二个元素开始检查递减情况，同样不满足递增
                return False
        elif current.data > previous.data:
            # 同样检查递增情况
            if not (previous.data < current.data):
                return False

        previous = current
        current = current.next

    return True

用c语言算法判断单链表是否递增有序

在C语言中，判断一个单链表是否递增有序可以使用迭代或递归的方式。这里提供一种简单的迭代方法：

#include <stdio.h>
#include <stdbool.h>

// 定义链表节点结构体
typedef struct ListNode {
    int val;
    struct ListNode *next;
} ListNode;

// 判断链表递增有序的函数
bool isMonotonic(ListNode* head) {
    if (head == NULL || head->next == NULL) { // 如果链表为空或只有一个元素，直接返回真
        return true;
    }

    ListNode *prev = head;
    ListNode *current = head->next; // 当前节点

    // 比较当前节点与前一个节点的关系，如果递增则继续，递减则返回false
    while (current != NULL) {
        if (current->val < prev->val) { // 如果当前值小于前一个值，不是递增序列，返回false
            return false;
        }
        
        if (current->val > prev->val && current->val < prev->next->val) { // 如果中间有降序，也返回false
            return false;
        }
        
        prev = current;
        current = current->next;
    }

    return true; // 遍历结束，说明链表递增有序
}

// 测试样例
int main() {
    ListNode *head = createLinkedList({1, 2, 3, 4}); // 创建一个示例递增链表
    bool result = isMonotonic(head);
    printf("%s\n", result ? "递增有序" : "非递增有序"); // 打印结果

    return 0;
}

// 创建链表的辅助函数
ListNode* createLinkedList(int arr[], int n) {
    ListNode *head = NULL, *tail = NULL;
    for (int i = 0; i < n; ++i) {
        ListNode *node = malloc(sizeof(ListNode));
        node->val = arr[i];
        node->next = NULL;

        if (head == NULL) {
            head = tail = node;
        } else {
            tail->next = node;
            tail = node;
        }
    }
    return head;
}