C++链表Quick Sort异常：排序结果缺失所有作为pivot的节点值

问题根因 #

• 拆分左右子链后未按正确顺序将pivot节点插入到左右子链中间，原有逻辑要么将pivot同时赋值给左右子链导致逻辑冲突，要么直接跳过了pivot的拼接步骤，导致pivot节点丢失。
• divide函数末尾对空链的赋值逻辑存在错误：当lower为空时直接赋值lower = cmp，同时greater为空又赋值greater = cmp，会导致cmp同时属于两个子链，递归排序时出现地址冲突、节点丢失甚至死循环。
• 后续修改的版本仅拼接了lower和cmp，未将排好序的greater子链接在cmp之后，同时存在dummy节点未释放的内存泄漏问题，多余的dummy节点默认data值为0，导致输出出现异常的0值。

修复方案 #

1. 修正divide函数逻辑 #

仅处理左右子链的拆分，不将pivot赋值给任意子链，拆分完成后直接释放dummy节点，避免垃圾数据进入链表：

void divide(Link* sentinel, Link* cmp, Link*& lower, Link*& greater) {
    Link* lower_dummy = new Link, * greater_dummy = new Link;
    Link* lend = lower_dummy, * rend = greater_dummy;

    while (sentinel != nullptr) {
        if (sentinel == cmp) {
            sentinel = sentinel->next; 
            continue;
        }
        Link* tmp = sentinel;
        sentinel = sentinel->next;
        tmp->next = nullptr;
        if (tmp->data < cmp->data) {
            lend->next = tmp;
            lend = lend->next;
        } else {
            rend->next = tmp;
            rend = rend->next;
        }
    }
    // 剥离dummy节点并释放内存
    lower = lower_dummy->next;
    greater = greater_dummy->next;
    delete lower_dummy;
    delete greater_dummy;
    // 独立pivot节点，避免挂到其他子链
    cmp->next = nullptr;
}

2. 修正sort_q的拼接逻辑 #

递归排序完左右子链后，按「排序后左链 -> pivot -> 排序后右链」的顺序拼接：

Link* sort_q(Link* sentinel) {
    // 基线条件保持不变
    if (sentinel == nullptr || sentinel->next == nullptr) {
        return sentinel;
    }
    Link* lower = nullptr;
    Link* greater = nullptr;
    Link* cmp = sentinel;

    divide(sentinel, cmp, lower, greater);

    lower = sort_q(lower);
    greater = sort_q(greater);

    // 拼接左链和pivot
    Link* res = lower;
    if (res == nullptr) {
        res = cmp;
    } else {
        Link* tmp = lower;
        while (tmp->next != nullptr) tmp = tmp->next;
        tmp->next = cmp;
    }
    // 拼接pivot和右链
    cmp->next = greater;
    return res;
}

冗余代码清理 #

原有add_link函数和concatenate函数已不再需要，可直接删除。

运行结果 #

修复后运行代码可得到预期输出：

3
4
5
5
7
8
9
11

内容的提问来源于stack exchange，提问作者James Newman