Day107 | 147.对链表进行插入排序 | 简单选择、冒泡、直接插入

147. 对链表进行插入排序 - 力扣（LeetCode）

147题直接用插入排序就可以解决

简单选择排序

思路：

笔者的思路：比较简单粗暴，我新建一个链表res，然后遍历原来的链表head，找到一个最大值的结点的前驱结点p，就保存到temp中，然后把p->next节点删掉，然后就用头插法把temp->next插入新的链表res中

简单排序得知道已经排序过的序列的位置，而笔者用的是新创建的连接的虚拟头结点的res来表示已经排序好的序列的位置

也可以不用新的链表直接在原地修改，基本思路：

用sortedTail指针标记已经排序好的序列的最后一个节点

用四个指针进行标记，min标记最小值的节点，premin表示pre的前驱结点

cur用来遍历找最小值，precur表示cur的前驱结点和更新premin（有前驱结点好进行修改）

遍历过程中，如果cur的值比min的值小的话，就把min更新为cur

然后利用premin把min给删掉，把min给接到已排序链表的末尾，也就是sortedTail的后面

最后把sortedTail指针更新为min即可

完整代码：

笔者第一次写的代码

//简单选择排序
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        //虚拟头结点
        ListNode *t=new ListNode;
        //用来返回的链表的虚拟头结点
        ListNode *res=new ListNode;
        t->next=head;
        //原来链表全都删除完毕代表排序结束
        while(t->next!=nullptr)
        {
            int maxVal=INT_MIN;
            ListNode *p=t;
            //temp保存有最大值的节点，因为这个结点要从原来的链表中删除掉
            ListNode *temp=new ListNode;
            //找最大值
            while(p->next!=nullptr)
            {
                if(p->next->val>maxVal)
                {
                    maxVal=p->next->val;
                    temp=p;
                }
                p=p->next;
            }
            //删除原来的节点
            ListNode *add=temp->next;
            temp->next=temp->next->next;
            //插入到新的链表中
            add->next=res->next;
            res->next=add;
        }
        return res->next;
    }
};

在原地进行修改的代码

ListNode* selectionSort(ListNode* head) {
    ListNode dummy(0);                // 虚拟头节点
    dummy.next = head;
    ListNode *sortedTail = &dummy;   // 维护已排序部分的尾指针

    while (sortedTail->next) {        // 遍历未排序部分
        //这两个一个指向最小值节点，一个指向最小值节点的前驱结点
        ListNode *preMin = sortedTail, *minNode = sortedTail->next;
        //cur是用来遍历的指针，pre是cur的前驱节点，这两个是一起的
        ListNode *curr = minNode->next, *preCurr = minNode;

        // 寻找最小值节点及其前驱（时间复杂度O(n)）
        while (curr) {                // 遍历剩余未排序节点
            if (curr->val < minNode->val) {
                preMin = preCurr;     // 更新最小值前驱指针
                minNode = curr;       // 更新最小值节点指针
            }
            preCurr = curr;           // 前驱指针跟随移动
            curr = curr->next;        // 当前指针后移
        }

        // 将最小节点从原链表中移除
        preMin->next = minNode->next; // 断开原链

        // 将最小节点插入已排序链表的尾部
        minNode->next = sortedTail->next; // 保持未排序部分连接
        sortedTail->next = minNode;    // 插入到已排序末尾
        sortedTail = minNode;          // 更新尾指针
    }
    return dummy.next;
}

冒泡排序

太麻烦了不说了，大家自己看吧

ListNode* bubbleSort(ListNode* head) {
    if (!head || !head->next) return head;
    ListNode dummy(0);                // 虚拟头节点处理头指针变化
    dummy.next = head;
    bool swapped = true;
    ListNode* end = nullptr;          // 记录每轮冒泡的终止边界

    while (swapped) {
        swapped = false;
        ListNode *prev = &dummy;      // 前驱指针（关键修正点）
        ListNode *curr = prev->next;  // 当前指针

        while (curr->next != end) {   // 遍历至已排序边界前
            ListNode *next = curr->next;
            if (curr->val > next->val) {
                // 交换相邻节点（调整指针而非数据域）
                prev->next = next;     // 前驱连接下一节点
                curr->next = next->next;
                next->next = curr;
                // 更新标记和指针
                swapped = true;
                prev = next;          // 前驱指针后移
            } else {
                prev = curr;          // 无需交换则正常后移
                curr = curr->next;
            }
        }
        end = curr;                   // 更新排序边界
    }
    return dummy.next;
}

直接插入排序

这个比较好理解一些，直接插入排序就是先找插入位置，也就是下一次处理节点要插入到我们已经排序的子序列的哪里

用cur遍历要处理的结点，而因为我们要把cur所指向的结点插入到已经排好序的子序列中，所以要有一个next保存cur的next结点，否则处理完一个节点直接找不到后续节点了。而我们要找插入位置，那就是要在排好序的子序列中找到最后一个小于cur的结点，然后把cur插入到该节点的后面。

我们用pre表示这个结点，那么比较的时候就是pre->next->val和cur->val进行比较了，只有满足这个条件的时候pre才会往后移动，否则不移动

而while条件里面的pre->next不为nullptr对应的是cur的节点值大于已经排好序的子序列的全部的值

其余情况对应的是pre->next->val < curr->val

ListNode* insertionSort(ListNode* head) {
    ListNode dummy(0);                // 虚拟头节点
    ListNode *curr = head;            // 遍历原链表的指针

    while (curr) {                     // 逐个处理未排序节点
        ListNode *next = curr->next;   // 保存下一个待处理节点
        ListNode *pre = &dummy;        // 从虚拟头开始寻找插入位置

        // 寻找插入位置（时间复杂度O(n)）
        while (pre->next && pre->next->val < curr->val) {
            pre = pre->next;           // 移动至最后一个小于curr的节点
        }

        // 插入操作
        curr->next = pre->next;        // 将curr插入pre之后
        pre->next = curr;              // 更新前驱指针
        curr = next;                   // 处理下一个节点
    }
    return dummy.next;
}