37-对链表进行插入排序

自己的做法

算法思想

就是插入排序。

首先添加哑节点dummy到链表头部。

使用两个指针end和cur。end用来指向已排序好的链表的尾节点，cur指向待排序节点。

每当排序一个节点时，执行以下步骤：

1. 设置pre指针指向dummy，判断pre的next是否为cur，并且pre的下一个节点的值是否小于cur的值
2. 如果为true，则pre向后走一步
3. 如果false，则判断pre的next是否为cur，如果是，则cur应在已排序链表的末尾，即end节点的下一个节点，它已经在正确位置了，执行end = end->next，将end向后走一步
4. 如果pre的next不是cur，那么就应该将cur插入到pre后面，首先end节点的next节点应该指向cur的next，然后将cur的next指向pre的next，最后将pre的next指向cur，即执行：end->next = cur->next;cur->next = pre->next; pre->next =cur。
5. 结束上一步后，将cur指向end节点的下一个节点，即下一个待排序节点。

当cur为空时，循环结束，插入排序完成。

算法实现

class Solution {
public:
    static ListNode* insertionSortList(ListNode* head) {
        if(head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode * dummy = new ListNode();
        dummy->next = head;
        ListNode * end = head;
        ListNode * cur = end->next;
        while (cur) {
            ListNode * pre = dummy;
            while (pre->next != cur && pre->next->val < cur->val) {
                pre = pre->next;
            }
            if(pre->next == cur) {
                end = end->next;
            } else {
                end->next = cur->next;
                cur->next = pre->next;
                pre->next = cur;
            }
            cur = end->next;
        }
        return dummy->next;

    }
};

优化后的代码：即先判断end的值和cur的值，如果end的值小于等于cur的值，end向后走一步，而不需要循环。

class Solution {
public:
    static ListNode* insertionSortList(ListNode* head) {
        if(head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode * dummy = new ListNode();
        dummy->next = head;
        ListNode * end = head;
        ListNode * cur = end->next;
        while (cur) {
            if(end->val <= cur->val) {
                end = end->next;
            } else {
                ListNode * pre = dummy;
                while (pre->next->val < cur->val) {
                    pre = pre->next;
                }
                    end->next = cur->next;
                    cur->next = pre->next;
                    pre->next = cur;
            }
            cur = end->next;
        }
        return dummy->next;

    }
};

性能分析

时间复杂度：每排序一个节点，都需要从头遍历，找到大于该节点的第一个节点，所以平均时间复杂度应为：$O(n^2)$。

空间复杂度：$O(1)$。

参考方法相同。