判断单链表是否递增有序

判断单链表是否递增有序，通常可以采用迭代或递归的方式。以下是迭代方法的一个简单示例：

1. 遍历链表：创建两个指针，一个（快指针）每次移动两步，另一个（慢指针）每次移动一步。如果链表是递增排序的，那么在遍历过程中，慢指针始终会指向当前节点小于下一个节点的位置。

2. 比较节点值：当快指针到达链表末尾时，如果慢指针还未到达，说明链表还有未检查的元素，并且存在比当前值更大的元素，因此链表不是递增有序。如果慢指针已经到达链表末尾，说明所有元素都是按照递增顺序排列的。

以下是伪代码形式：

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

    slow = head
    fast = head.next

    while fast and fast.next:
        if slow.val > fast.val:
            return False
        slow = slow.next
        fast = fast.next.next

    return True

相关问题

判断单链表是否递增有序，用c语言简单易懂的方法

判断单链表是否递增有序可以采用迭代或递归的方式。这里提供一种简单的迭代方法：

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

// 定义链表节点结构体
typedef struct ListNode {
    int val;   // 节点值
    struct ListNode* next; // 指向下一个节点的指针
} ListNode;

bool isMonotonic(ListNode* head) {
    if (head == NULL || head->next == NULL) { // 如果链表为空或只有一个元素
        return true;
    }

    // 初始化两个指针，一个正常移动，一个检查前一个节点是否大于等于当前节点
    ListNode* slow = head;
    ListNode* fast = head->next;
    
    while (fast && fast->next) {
        if (slow->val > fast->val) { // 如果有降序情况，直接返回false
            return false;
        } else if (slow->val < fast->val) { // 如果有升序情况，调整快指针到下一组对比
            slow = fast;
            fast = fast->next->next;
        } else {
            // 同步慢指针和快指针
            slow = slow->next;
            fast = fast->next->next;
        }
    }

    return true; // 如果遍历完整个链表都没有发现逆序，说明它是递增有序的
}

int main() {
    // 创建示例链表并测试函数
    ListNode* list = createLinkedList(); // 假设createLinkedList()函数已创建了一个链表
    bool result = isMonotonic(list);
    printf("Is the linked list monotonic? %s\n", result ? "Yes" : "No");
    return 0;
}

用c语言写一段详细的代码判断单链表是否递增有序

在C语言中，我们可以编写一个函数来检查单链表是否递增有序。递增有序意味着列表中的每个节点值都大于其前一个节点值。这里是一个简单的函数，它会遍历链表并比较相邻节点的值：

#include <stdbool.h>  // 包含布尔类型 bool 和 true 宏

typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 函数声明：检查链表是否递增有序
bool is_sorted_increasing(Node* head) {
    if (head == NULL || head->next == NULL) {
        return true;  // 空链表或只有一个元素都是递增有序的
    }

    Node* current = head;
    while (current->next != NULL) {
        // 检查当前节点是否大于前一个节点
        if (current->data <= current->next->data) {
            return false;  // 发现不递增，直接返回false
        }
        current = current->next;  // 移动到下一个节点
    }

    return true;  // 遍历完整个链表，没有发现不递增的情况，所以返回true
}

// 示例：创建并测试一个递增有序和一个非递增有序的链表
int main() {
    Node* sorted_list = create_sorted_list(1, 2, 3, 4, 5);  // 递增有序链表
    Node* unsorted_list = create_unsorted_list(1, 3, 2, 6, 4);  // 非递增有序链表

    printf("Is the sorted list increasing? %s\n", is_sorted_increasing(sorted_list) ? "Yes" : "No");
    printf("Is the unsorted list increasing? %s\n", is_sorted_increasing(unsorted_list) ? "Yes" : "No");

    return 0;
}

// 辅助函数：创建已知顺序的链表
Node* create_sorted_list(int* data, int length) {
    Node* head = NULL;
    Node* temp = NULL;
    
    for (int i = 0; i < length; i++) {
        Node* newNode = create_node(data[i]);
        if (head == NULL) {
            head = newNode;
        } else {
            temp->next = newNode;
        }
        temp = newNode;
    }
    return head;
}

// 辅助函数：创建链表
Node* create_node(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode != NULL) {
        newNode->data = data;
        newNode->next = NULL;
    } else {
        printf("Memory allocation failed.\n");
    }
    return newNode;
}

这个程序包含了一个主函数，其中创建了两个链表（一个是递增有序，另一个不是），然后分别使用 `is_sorted_increasing` 函数检查它们是否递增有序。