已知长度为n的顺序表L，其数据元素类型为整型，设计一个时间复杂度为O(n)、空间复杂度为O(1)的算法，将L中所有小于k的整数放在表的前半部分，大于等于k的整数放在后半部分。不改变原来的排序。思路：获取k值的位置，遍历整个表，小于k的插在k前面，大于k的插结尾。用顺序表c语言写

在 C 语言中，我们可以使用两个指针 `index` 和 `i` 来实现这个算法。`index` 用于追踪 `k` 应该插入的位置，`i` 从表头开始遍历。以下是详细的步骤：

#include <stdio.h>
#include <stdlib.h>

// 定义顺序表的节点结构体
typedef struct ListNode {
    int data;
    struct ListNode *next;
} ListNode;

// 插入节点到有序表中
void insertIfSmaller(ListNode** head, int data, int k) {
    // 当找到第一个大于等于k的位置或者到达表尾
    while (*head && (*head)->data >= k) {
        // 将当前节点移到下一个位置
        ListNode *temp = *head;
        *head = (*head)->next;
        // 更新已插入位置指针
        if (*head)
            (*head)->prev = temp;
        else
            // 如果这是第一个节点，它没有 prev
            temp->prev = NULL;
        temp->next = NULL;
    }
    
    // 插入新节点
    if (!(*head)) {
        // 如果k是第一个元素
        *head = (ListNode*)malloc(sizeof(ListNode));
        if (*head)
            (*head)->data = data;
        (*head)->next = (*head)->prev = NULL;
    } else {
        temp->next = (ListNode*)malloc(sizeof(ListNode));
        if (temp->next)
            temp->next->data = data;
        temp->next->prev = temp;
        temp->next->next = NULL;
    }
}

void printList(ListNode *head) {
    ListNode *temp = head;
    while (temp) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
}

// 主函数示例
int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    ListNode *head = NULL;
    for (int i = 0; i < n; i++) {
        int data;
        scanf("%d", &data);
        insertIfSmaller(&head, data, k);
    }
    printList(head);
    return 0;
}

这个算法的工作原理是，当遍历到某个节点时，如果它的值大于等于 `k`，就将这个节点移动到 `k` 应该插入的位置之后，同时保持有序。当遇到小于 `k` 的值时，直接插入到当前位置。由于我们不需要创建新的数组或复制数据，所以时间和空间复杂度都是 O(n)。如果你对这个算法还有疑问，可以问我：