使用辅助列表对链接列表进行快速排序

Question

我需要在链表上执行快速排序，问题是我不知道如何连接列表的小边、枢轴和大边。

分区函数有效，我每次都可以划分列表，直到基本情况。

关于问题要求的几点说明：

• 我必须拆分列表（示例如下）。
• 枢轴始终是第一个元素。
• 连接各部分后，原始列表的指针应指向排序列表

例如：

原名单：

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

代码：

void partition(list **lst, list **pivot, list **small, list **big)
{
    // your code:
    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;
    }

    // Close the links
    pivotEl->next = NULL;

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

    // connects to the lists
    *pivot = pivotEl;
    *small = smallHead;
    *big = largeHead;
}

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);
    }
}

Answer 1

您可以定义此函数，用另一个链表扩展链表。这里没有魔法：您必须遍历第一个列表才能找到它的尾部，然后将尾部的

next

字段设置为下一个列表的头部。如果第一个列表为空，则该列表的头指针必须更改为另一个列表的头：

void concat(list **lst, list *other) {
    if (*lst) {
        list *cur = *lst;
        while (cur->next) {
            cur = cur->next;
        }
        cur->next = other;
    } else {
        *lst = other;
    }
}

现在你的

quickSortList

功能可以完成如下：

        pivot->next = big; // Or: concat(&pivot, big);
        concat(&small, pivot);
        *lst = small;

请注意，我们可以确定

pivot

是一个只有一个元素的列表，因此我们实际上不需要依赖

concat

将其与

big

链接。对其

next

字段进行简单的赋值即可达到目的。

嵌入代码

在评论中您写道“无法使用其他辅助功能”。我认为你没有理由不采用良好的实践，但这里的原则与一个代码块相同：

        pivot->next = big;
        if (small) {
            list *cur = small;
            while (cur->next) {
                cur = cur->next;
            }
            cur->next = pivot;
            *lst = small;
        } else {
            *lst = pivot;
        }