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

这个问题描述的是快速排序算法的一个变种，称为“分区”操作，目的是将链表分割成两个子链表，使得所有小于`Ki`的关键字都在左侧，而大于等于`Ki`的关键字在右侧。这是一个经典的二分查找的思想应用在链表上。

在C++中，你可以使用双指针法来解决这个问题，这里是一个简单的链表版本的代码示例：

#include <iostream>
using namespace std;

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

ListNode* partition(ListNode* head, ListNode* tail, int key) {
    ListNode* pivot = new ListNode(key); // 创建一个虚拟头节点作为基准
    pivot->next = head; // 将基准插入到链表头部

    ListNode* less = pivot; // 初始化指向小于基准节点的指针
    ListNode* greater = pivot->next; // 初始化指向大于等于基准节点的指针

    while (greater != tail) {
        if (greater->val < key) { // 如果当前节点值小于key，交换位置
            swap(less->next, greater);
            less = less->next;
        } else {
            greater = greater->next; // 否则继续比较下一个节点
        }
    }

    return less->next; // 返回新的分隔点，即`greater`指针所指向的位置
}

void quickPartition(ListNode*& head, ListNode* tail) {
    if (head == nullptr || head->next == nullptr) return; // 特殊情况处理
    ListNode* pivotKey = tail->val; // 将尾部元素作为临时基准
    tail = partition(head, tail, pivotKey); // 分区并更新tail指针
    quickPartition(head, tail); // 对剩余部分递归调用
}

int main() {
    ListNode* list = /* 初始化你的链表 */;
    // ...假设list已经包含有数据...
    
    quickPartition(list, NULL); // 调用快速分区函数
    // ...后续处理，例如打印左右子链表...

    return 0;
}

这个代码首先创建一个临时的"pivot"节点，并将其插入到链表开头。然后通过遍历链表，根据节点值与基准的关系调整节点位置，最后返回新的分界点。注意这里的递归调用会持续进行，直到链表分为左右两个非空的部分。