设单链表L非递减有序、试写算法将X插入、仍保持L的有序性

1. 如果链表为空，直接将X插入作为头结点。
2. 如果X小于等于头结点的值，将X插入作为新的头结点。
3. 如果X大于头结点的值，从头结点开始遍历链表：
- 如果遍历到链表末尾，将X插入作为新的尾结点。
- 如果遍历到某个结点的值大于X，将X插入到该结点之前。
4. 返回链表。

代码实现：

def insert_in_order(L, X):
    if not L:  # 链表为空，将X插入作为头结点
        L = Node(X)
    elif X <= L.val:  # X小于等于头结点的值，将X插入作为新的头结点
        new_node = Node(X)
        new_node.next = L
        L = new_node
    else:  # X大于头结点的值，从头结点开始遍历链表
        curr = L
        while curr.next and curr.next.val < X:
            curr = curr.next
        new_node = Node(X)
        new_node.next = curr.next
        curr.next = new_node
    return L

相关问题

C语言：设单链表L是一个递减有序表，试写一算法将X插入其中仍保持L的有序性

以下是C语言实现的算法：

void insertNode(struct ListNode **head, int x) {
    struct ListNode *newNode = (struct ListNode *)malloc(sizeof(struct ListNode));
    newNode->val = x;
    newNode->next = NULL;
    struct ListNode *prev = NULL;
    struct ListNode *curr = *head;
    while (curr != NULL && curr->val > x) {
        prev = curr;
        curr = curr->next;
    }
    if (prev == NULL) { // x应插入到头部
        newNode->next = *head;
        *head = newNode;
    } else { // x应插入到prev和curr之间
        prev->next = newNode;
        newNode->next = curr;
    }
}

解释：

- `struct ListNode` 是单链表结点的结构体定义。
- `insertNode` 函数接受一个指向单链表头结点的指针和待插入的整数 x。
- 首先创建一个新的结点 `newNode`，保存 x，将它的下一个结点设为 NULL。
- 接着遍历链表，找到第一个小于等于 x 的结点 curr 和它的前一个结点 prev。
- 如果 prev 为 NULL，说明 x 应该插入到头部，将新结点的下一个结点设为原头结点，然后将头结点指向新结点。
- 否则，将新结点插入到 prev 和 curr 之间。

这样，就可以将 x 插入到 L 中，并保持 L 的递减有序性。

设顺序表l是一个递减有序表，试写一算法，将x插入其后仍保持l的有序性

算法如下：

1. 定义变量i为顺序表l的长度-1，j为i+1。

2. 若j等于顺序表l的容量，则输出“顺序表已满，无法插入”。

3. 若x小于等于顺序表l的最后一个元素，则输出“插入元素应大于顺序表最后一个元素”。

4. 从i开始向前遍历顺序表l，若x小于等于当前元素，则将当前元素后移一位。

5. 将x插入到j位置。

6. 返回顺序表l。

算法实现：

void insert(int l[], int x, int len) {
    int i = len - 1, j = i + 1;
    if (j == MAXSIZE) {
        printf("顺序表已满，无法插入\n");
        return;
    }
    if (x <= l[i]) {
        printf("插入元素应大于顺序表最后一个元素\n");
        return;
    }
    while (i >= 0 && x <= l[i]) {
        l[j] = l[i];
        i--;
        j--;
    }
    l[j] = x;
}

其中，MAXSIZE为顺序表的容量。