设有一组初始记录关键字序列(K1,K2,…,Kn),要求设计一个算法能够在O(n)的时间复杂度内将线性表[1]划分成两部分,其中左半部分的每个关键字均小于Ki,右半部分的每个关键字均大于等于Ki。c语言代码

这个问题描述的是二分查找法的一个应用场景，我们通常称之为“排序链表”或者“分割链表”。为了在O(n)时间复杂度内完成这个任务，我们可以使用迭代的方式来实现：

首先，我们需要定义一个链表节点结构体，假设包含整型数据key和指向下一个节点的指针next。

typedef struct ListNode {
    int key;
    struct ListNode* next;
} ListNode;

接下来，编写一个函数`splitList`，它接收一个链表头结点`head`和目标关键字`Ki`作为输入：

ListNode* splitList(ListNode* head, int Ki) {
    ListNode* left = NULL, *right = NULL, *current = head;

    // 迭代遍历链表
    while (current != NULL) {
        if (current->key < Ki) {
            // 如果当前元素小于Ki，将其添加到left链表
            if (left == NULL) {
                left = current;
            } else {
                left->next = current;
                left = left->next;
            }
        } else {
            // 否则，如果当前元素大于等于Ki，将其添加到right链表
            if (right == NULL) {
                right = current;
            } else {
                right->next = current;
                right = right->next;
            }
        }

        current = current->next;  // 移动到下一位
    }

    // 将两个链表连接起来
    if (left != NULL) {
        left->next = right;
    }

    return right;
}

这个函数会在遍历完整个链表之后返回分割后的右半部分链表的头结点，左半部分链表会保持原样。整个过程的时间复杂度为O(n)，因为只遍历了一次链表。