程序员代码面试指南 2.16：单链表的选择排序

1、思路

• 将链表分为已排序和未排序两个部分，循环遍历未排序部分找到最小值，将其从未排序链表中删除并添加到已排序链表末尾；

• 为了实现删除最小值节点的操作，需要保存最小值节点的前一个节点；

• 时间复杂度为 ，空间复杂度为 。

2、代码

//在未排序链表中找到最小值节点的前一个节点
list_node * getSmallestPreNode(list_node *head)
{
    list_node *smallPre = nullptr, *small = head, *pre = head, *cur = head->next;

    while (cur != nullptr)
    {
        if (cur->val < small->val)  //找到值更小的节点，更新指针
        {
            smallPre = pre;
            small = cur;
        }

        pre = cur;
        cur = cur->next;
    }

    return smallPre;
}

list_node * selection_sort(list_node * head)
{
    //smallPre为最小值节点的前一个节点，small为最小值节点
    list_node *tail = nullptr, *cur = head, *smallPre = nullptr, *small = nullptr;

    while (cur != nullptr)
    {
        small = cur;
        smallPre = getSmallestPreNode(cur);
        if (smallPre != nullptr)
        {
            small = smallPre->next;
            smallPre->next = small->next;       //这一步在未排序链表中删除了最小值节点
        }

        //若当前节点为最小值节点，则前进到下一节点
        cur = cur == small ? cur->next : cur;
        if (tail == nullptr)
        {
             head = tail = small;               //创建头结点
        }
        else
        {
            tail = tail->next = small;          //将最小值节点接到尾部
        }

    }

    return head;
}