数组原地分区保序算法实现及单链表移植与优化咨询

问题1：该数组版本算法能否移植到单链表场景？ #

不建议直接移植。你当前的数组版本核心逻辑是找到后置的小于x的元素后，通过平移i到j之间的所有元素，把该元素挪到前部分区的末尾。单链表没有随机访问特性，要完成相同的平移操作，你需要遍历i到j区间的所有节点，时间复杂度和数组版本一致为O(n²)，完全浪费了单链表只需修改指针就能调整节点位置的优势，实际运行效率会非常低。

问题2：是否存在更优的实现方案？ #

分场景给你提供更优方案：

单链表场景（你的原需求，O(n)时间、O(1)空间、稳定分区） #

这是效率最高的实现，完全不需要改动节点值，仅调整指针即可：

• 初始化两个虚拟头节点，分别对应小于x的分区和大于等于x的分区，同时维护两个分区的尾指针方便尾插
• 一次遍历原链表，根据节点值大小将其尾插到对应分区的尾部
• 遍历结束后，将小于x分区的尾指针指向大于等于x分区的首节点，将大于等于x分区的尾指针的next置为nullptr避免环
• 最终返回小于x分区的首节点即可
  这个方案天然保证两个分区的元素相对顺序和原始顺序一致，时间复杂度仅为O(n)，空间复杂度为O(1)（仅使用固定数量的指针变量，无额外空间开销）。

参考单链表实现代码：

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

ListNode* partition(ListNode* head, int x) {
    ListNode less_dummy, ge_dummy;
    ListNode *less_tail = &less_dummy, *ge_tail = &ge_dummy;
    ListNode *cur = head;
    while (cur != nullptr) {
        if (cur->val < x) {
            less_tail->next = cur;
            less_tail = less_tail->next;
        } else {
            ge_tail->next = cur;
            ge_tail = ge_tail->next;
        }
        cur = cur->next;
    }
    // 拼接两个分区
    less_tail->next = ge_dummy.next;
    ge_tail->next = nullptr;
    return less_dummy.next;
}

数组场景优化 #

如果你需要优化数组版本的效率：

• 允许额外空间的情况下，最优方案是O(n)时间、O(n)空间：开两个临时数组分别存储两个分区的元素，遍历原数组完成分类后，再按顺序写回原数组即可
• 要求必须原地实现的话，目前最优的稳定原地分区算法时间复杂度为O(n log n)，可以参考稳定快速排序的分区逻辑，实现相对复杂。

内容的提问来源于stack exchange，提问作者infernus-85