链表快速排序：如何合并小链表、基准链表与大链表

问题背景 #

我需要对链表实现快速排序，但卡在了小链表、基准链表和大链表的拼接环节。已知partition函数可以正常工作，能将链表拆分为基准元素、小于等于基准的链表、大于基准的链表。

需求说明 #

• 必须拆分链表（示例如下）
• 基准（pivot）始终为第一个元素
• 拼接各部分后，原链表的指针需指向排序后的链表

示例 #

原链表：5->3->7->1->9->8->2->5->6

• 基准链表：5->NULL
• 小于等于基准的链表：3->1->2->5（首次拆分后需继续递归拆分至基准情况）
• 大于基准的链表：7->9->8->6（首次拆分后需继续递归拆分至基准情况）
• 首次拆分后原链表：NULL
• 最终结果：1->2->3->5->5->6->7->8->9->NULL

现有代码 #

可正常工作的partition函数 #

void partition(list **lst, list **pivot, list **small, list **big)
{
    list *curr, *pivotEl, *smallHead, *smallTail, *largeHead, *largeTail;

    pivotEl = *lst;
    curr = (*lst)->next;

    smallHead = smallTail = largeHead = largeTail = NULL;

    while (curr != NULL)
    {
        if (curr->data <= pivotEl->data)
        {
            if (smallHead == NULL)
            {
                smallHead = curr;
                smallTail = curr;
            }
            else
            {
                smallTail->next = curr;
                smallTail = curr;
            }
        }
        else
        {
            if (largeHead == NULL)
            {
                largeHead = curr;
                largeTail = curr;
            }
            else
            {
                largeTail->next = curr;
                largeTail = curr;
            }
        }

        curr = curr->next;
    }

    // 截断各链表的尾部
    pivotEl->next = NULL;

    if (smallTail != NULL) smallTail->next = NULL;
    if (largeTail != NULL) largeTail->next = NULL;

    // 赋值给输出参数
    *pivot = pivotEl;
    *small = smallHead;
    *big = largeHead;
}

存在问题的quickSortList函数 #

void quickSortList(list **lst) // here is i am stuck
{
    // your code:
    list *temp = *lst, *big, *small, *pivot;

    if (temp && temp->next)
    {
        partition(lst, &pivot, &small, &big);
        quickSortList(&small);
        quickSortList(&big);
    } 
    else {
        pivot->next = big;
        if (small) 
        {
          list* cur = small;
          while (cur->next) {
            cur = cur->next;
        }
        cur->next = pivot;
        *lst = small;
    }
    else {
        *lst = pivot;
    }


}

问题分析与修正 #

原quickSortList的核心问题是拼接逻辑的位置错误，且边界处理存在未定义行为：

1. 拼接代码被放在了链表长度≤1的else分支中，而实际上应该在递归处理完small和big链表后执行
2. else分支中pivot变量未初始化，直接访问会导致程序崩溃或异常

修正后的quickSortList函数 #

void quickSortList(list **lst)
{
    list *temp = *lst, *big, *small, *pivot;

    // 递归终止条件：链表为空或只有一个节点，无需排序
    if (!temp || !temp->next)
    {
        return;
    }

    // 拆分链表为基准、小链表、大链表
    partition(lst, &pivot, &small, &big);

    // 递归排序小链表和大链表
    quickSortList(&small);
    quickSortList(&big);

    // 拼接三部分：小链表 -> 基准 -> 大链表
    if (small)
    {
        // 找到小链表的尾节点
        list *cur = small;
        while (cur->next != NULL)
        {
            cur = cur->next;
        }
        // 小链表尾部连接基准
        cur->next = pivot;
        // 原链表指针指向小链表头部（即整个排序后的链表头部）
        *lst = small;
    }
    else
    {
        // 没有小链表，直接以基准为头部
        *lst = pivot;
    }

    // 基准尾部连接大链表
    pivot->next = big;
}

修正说明 #

1. 递归终止条件：明确判断链表为空或只有一个节点时直接返回，无需处理
2. 拆分与递归：先拆分链表，再递归排序小链表和大链表
3. 拼接逻辑：
   • 如果存在排序后的小链表，找到其尾节点并连接到基准节点，原链表指针指向小链表头部
   • 如果没有小链表，原链表指针直接指向基准节点
   • 最后将基准节点的尾部连接到排序后的大链表
4. 原链表指针更新：确保*lst最终指向排序后的整个链表的头部

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