算法设计题：设有一组初始记录关键字序列为（K1 ，K2 ，… ，Kn），要求设计一个算法能 够在 O（ n）的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小 于 Ki，右半部分的每个关键字均大于等于 Ki。c++链表代码

这个问题可以使用双指针法（也叫快慢指针）来解决，同时利用链表的特点。首先创建两个指针，一个普通指针`slow`初始化为头节点，另一个快速指针`fast`初始化为头节点。当`fast`指向的元素大于等于`Ki`时，移动`fast`到下一个节点；如果小于`Ki`，则将当前节点作为右半部分的结果并移动`slow`。这样，在遍历完整个链表的过程中，`slow`的位置就是分界点。

以下是C++链表版本的代码示例：

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode* partition(ListNode* head, int K) {
    if (!head || !head->next) return head;

    ListNode *slow = head, *fast = head;
    while (fast && fast->val >= K) {
        fast = fast->next;
        if (fast) fast = fast->next; // 跳过大于等于K的部分两次
    }
    if (fast) slow = fast;

    ListNode* pivot = slow->next;
    slow->next = nullptr; // 断开左右部分连接

    return insertAfter(head, pivot);
}

ListNode* insertAfter(ListNode* prev, ListNode* node) {
    if (!prev) return node;
    prev->next = node;
    return node;
}

这个函数首先找到需要分割的位置，然后通过`insertAfter`辅助函数将找到的节点插入到原链表的中间位置，返回新的链表头部。