单链表的直接插入排序

本文将图解LeetCode上面的一道基于单链表的直接插入排序的题

知识回顾

来自LeetCode的一道题对链表进行直接插入排序

输入格式

列表中的节点数在 [1, 5000]范围内
-5000 <= Node.val <= 5000

输入样例和输出结果

1 2	`输入: head = [4,2,1,3] 输出: [1,2,3,4]`

以上面这个输入为例子，下面是表示图：
绿色：代表已经排序好的有序序列的元素

褐色：代表base即待插入的元素

红色：代表变量关系

算法思路图示 + 表述如下：

顺序情况很容易理解，因为直接插入排序就是维护一个有序序列的过程。

我们来分析逆序情况：

画五角星的这轮，实际上是最容易提取出 task 步骤的，请关注这一轮操作。

转换成部分代码：

if(sortedTail -> val <= base -> val){
    // 顺序
    sortedTail = sortedTail -> next; // sortedTail 后移一位    
}else{
    // 逆序 （此处也是关注重点）
    // pre处 是插入点（后插），需要循环找出来，因此 dummy 的重要性就体现出来了
    // 毕竟在这个过程有一个极小的数，需要放在第一个位置，你怎么插？
    ListNode * pre = dummy;
    // 过滤掉比base小的，使用 pre -> next -> val 的值来过滤，这样就能求出 插入点
    while(pre -> next -> val <= base -> val) pre = pre -> next;
    // 现在 pre 处就是插入点了（后插）
    // 插入三部曲，图示很清楚
    sortedTail -> next = base -> next;
    base -> next = pre -> next;
    pre -> next = base;
}

至此，我们实现了step 1 和 step 2 了。

完整代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        // 如果头结点为空或者只有一个结点，则直接返回头结点
        if (!head || !head->next) return head;

        // 虚拟头结点，方便操作
        ListNode * dummy = new ListNode(0, head);
        
        // 直接插入排序：① 默认第1个元素有序。② 第2个元素是 base
        // sortedTail: 有序序列中的 最后一个结点, 在这也是元素中第1个结点
        // base：第2个元素，也是待插入元素
        ListNode * sortedTail = head, * base = head -> next;

        // 当base不为空，则一直是排序状态
        while(base){
            // base 与 sortedTail比较
            // 产生两种情况 (1. 顺序 2. 逆序)

            
            if(sortedTail -> val <= base -> val){
                // 顺序
                sortedTail = sortedTail -> next; // sortedTail 后移一位    
            }else{
                // 逆序，执行 task 步骤
                ListNode * pre = dummy;
                // 过滤掉比 base 小的值，pre就是插入的位置
                while(pre -> next -> val <= base -> val) pre = pre -> next;

                // 插入三部曲
                sortedTail -> next = base -> next;
                base -> next = pre -> next;
                pre -> next = base;
            }
            // 注意：base总是 sortedTail的next，不能写成 base = base -> next
            base = sortedTail -> next;
        }
        // 去掉dummy，返回排序后的链表
        return dummy -> next;
    }
};

复杂度分析

时间复杂度：
对于链表而言，插入元素时只要更新相邻节点的指针即可，不需要像数组一样将插入位置后面的元素往后移动，因此插入操作的时间复杂度是O(1)，但是找到插入位置需要遍历链表中的节点，时间复杂度是O(n)，因此链表直接插入排序的总时间复杂度仍然是O(n²)。
空间复杂度：
整个排序过程中需要的额外辅助空间为 dummy，sortedTail，base，pre。
使用常数大小的额外空间，空间复杂度为O（1）