[数据结构与算法]147. 对链表进行插入排序 ●●

147. 对链表进行插入排序 ●●

描述

给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头节点 。

示例

输入: head = [-1,5,3,4,0]
输出: [-1,0,3,4,5]

题解

1. 从前往后找插入点

插入排序的基本思想是，维护一个有序序列，初始时有序序列只有一个元素，对于每个未排序序列中的元素，在有序序列中找到其对应的插入位置并插入，将有序序列的长度增加 1，直到全部元素都加入到有序序列中。

如果是 数组 的插入排序，则数组的前面部分是有序序列，每次找到有序序列后面的第一个元素（待插入元素）的插入位置，将有序序列中的插入位置后面的元素都往后移动一位，然后将待插入元素置于插入位置。

对于 链表 而言，插入元素时只要更新相邻节点的指针即可，不需要像数组一样将插入位置后面的元素往后移动，因此插入操作的时间复杂度是 O(1)，但是找到插入位置需要遍历链表中的节点，时间复杂度是 O(n)，因此链表插入排序的总时间复杂度仍然是 $O(n^2)$，其中 n 是链表的长度。

对于单向链表而言，只有指向后一个节点的指针，因此需要从链表的头节点开始往后遍历链表中的节点，寻找插入位置。

算法中用到虚拟头结点 dummyHead 进行辅助操作；

同时利用 tail 变量记录有序链表的尾节点，对于新的元素，先与尾节点比较后再进行插入操作可节省时间。

• 时间复杂度：$O(n^2)$，其中 n 是链表的长度。
• 空间复杂度：$O(1)$。

class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        ListNode* dummyHead = new ListNode(-1, head);
        ListNode* tail = head;                          // tail 为有序链表的尾节点
        ListNode* curr = head->next;
        while(curr != nullptr){
            if(curr->val < tail->val){                  // 插入位置在有序序列中间
                ListNode* prev = dummyHead;
                while(curr->val > prev->next->val){
                    prev = prev->next;                  // 找到插入位置
                }
                tail->next = curr->next;                // 实现插入操作
                curr->next = prev->next;
                prev->next = curr;
            }else{                                      // 当前节点大于尾节点，不需要插入，直接更新尾节点
                tail = curr;
            }
            curr = tail->next;                          // 遍历插入下一个节点
        }
        return dummyHead->next;
    }
};