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

在 C 语言中，我们可以使用链表来实现这个需求，具体步骤如下：

1. **初始化链表**：首先，我们需要创建一个包含 `K` 的节点结构体，比如 `Node` 结构，包含一个整数值 `key` 和指向下一个节点的指针 `next`。

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

2. **构建初始链表**：由于所有节点的值都是 `K`，我们可以在主函数中创建并连接节点，直到达到所需的长度。

Node* createList(int K, int n) {
    Node* head = (Node*)malloc(sizeof(Node));
    Node* tail = head;

    for (int i = 0; i < n; ++i) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->key = K;
        newNode->next = NULL;

        if (i == 0)
            head = newNode;
        else
            tail->next = newNode;

        tail = newNode;
    }
    return head;
}

3. **划分链表**：遍历链表，找到第一个大于或等于 `Ki` 的节点。我们可以设置两个指针 `prev` 和 `curr`，分别指向当前节点的前一个和当前节点。当 `curr->key >= Ki` 时，我们将从 `prev` 开始到 `curr` 分割链表，并更新左右链表的头结点。

void partition(Node** leftHead, Node** rightHead, Node* curr, int Ki) {
    if (!curr) return;

    Node* prev = curr->prev;
    Node* tempRightHead = *rightHead;

    while (curr && curr->key < Ki) {
        prev = curr;
        curr = curr->next;
    }

    // 如果找到了满足条件的节点，将之前的部分连接到右边
    if (prev) {
        prev->next = NULL;
        *rightHead = curr;
    } else {
        *leftHead = curr;
    }

    // 将剩余节点添加到右边链表
    if (tempRightHead) {
        curr->next = tempRightHead;
    }
}

4. **返回结果**：最后，你需要分别返回左右链表的头指针。

void splitList(Node** leftHead, Node** rightHead, Node* head, int Ki) {
    *leftHead = head;
    *rightHead = NULL;
    Node* curr = head;

    while (curr) {
        partition(leftHead, rightHead, curr, Ki);
        curr = curr->next;
    }
}

// 使用示例
int main() {
    int K = 5;
    int n = 10; // 假设有10个节点
    Node* list = createList(K, n);

    // 省略分配存储空间、显示分割后的链表等细节...

    return 0;
}