欢迎关注 leetcode 专栏

题目

对链表进行插入排序。

插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。
每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。

插入排序算法：

插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
重复直到所有输入数据插入完为止。

示例 1：

输入: 4->2->1->3
输出: 1->2->3->4

示例 2：

输入: -1->5->3->4->0
输出: -1->0->3->4->5

输入的节点对象的定义

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

链接：https://leetcode-cn.com/problems/insertion-sort-list

解法

常规解法

思路：

考虑到链表的表头可能常常会变化，不利于维护，因此可创建一个永远不会被替换的表头 ListNode(float('-inf'))，每次从该表头开始比较
插入排序的子问题，就是将待排序的节点 current_node 插入到已排序区，因此首先要在已排序区找到最后一个小于等于 current_node 值的节点 cur ，并将 current_node 插入到 cur 后面，以保持排序的稳定性。
定义当前已排序区的最后一个节点是 last，如果 cur 是 last，那么相当于什么都不用动，且 current_node 变成了新的 last ；如果不是，则插入 current_node 到 cur 后面，并更新 last 的指针。

class Solution:
    def insertionSortList(self, head: ListNode) -> ListNode:
        if not head: return None
        
        # 创建一个永远不会被替换的假头
        new_head = ListNode(float('-inf'))
        new_head.next = head
        
        last = head # 已排序区的最后一个节点，初始化为 head
        while last.next: 
            # 待排序的节点
            current_node = last.next 
            
            # 找到 current_node 的前一个节点 cur，小于等于是为了保持排序的稳定
            # 如果已排序区的值都 <= current_node ，则 cur 为 last
            # 如果已排序区存在大于 current_node 的节点，则 cur 会变成该节点的前一个节点
            cur = new_head
            while cur != last and cur.next.val <= current_node.val:
                cur = cur.next
            
            # 插入 current_node 到正确位置
            if cur == last:
                # 更新已排序区的最后一个节点
                last = current_node
            else:
                # 先把 current_node 从链表中分离出来
                last.next = current_node.next
                # 再插入 current_node 到 cur 与 cur.next 之间
                current_node.next = cur.next
                cur.next = current_node                

        return new_head.next

空间复杂度 O(1)，只是额外申请了几个变量的空间。
时间复杂度 O(N^2)：

最好情况下，当原来的链表是逆序时，每次在已排序区只需要比较1次，总共只需要比较 N - 1 次，时间复杂度仅为 O(n)。
最差情况下，当原来的链表是升序时，对于第 i 个数，需要比较 i - 1 次，总共需要比较 N*(N-1)/2 次，时间复杂度为 O(n^2)。
当链表是杂乱无章时，时间复杂度为 O(n^2)。

数组解法

可以考虑先将链表转化成数组，然后对数组使用插入排序，再重新转化为链表。

# 数组解法
class Solution:
    def insertionSortList(self, head: ListNode) -> ListNode:
        if not head: return None
        
        # 将节点放入数组
        nodes = []
        node = head
        while node:
            nodes.append(node)
            node = node.next
        
        # 排序数组
        # nodes = sorted(nodes, key=lambda x: x.val)
        self.insertion_sort(nodes)

        # 更新指针
        for prev, cur in zip(nodes, nodes[1:]):
            prev.next = cur
            cur.next = None

        return nodes[0]
    
    def insertion_sort(self, arr): 
        for i in range(1, len(arr)): 
            key = arr[i] 
            j = i-1
            while j >= 0 and key.val < arr[j].val :
                arr[j + 1] = arr[j] 
                j -= 1
            arr[j + 1] = key

空间复杂度 O(N)，创建了一个长度为 N 的数组。
时间复杂度 O(N*logN)，分为三个部分：

遍历一遍并插入到数组中，遍历的时间复杂度为 O(N)
排序的复杂度，如果用插入排序的话就是 O(N^2)
更新指针，复杂度也是 O(N)

如果把排序部分用归并排序或快排来实现的话，总体的时间复杂度就可以降为 O(N*logN)。

执行时间差这么多，有点奇怪，看了 leetcode 评论区，有人说是测试集有问题，好吧~

更多刷题，尽在 leetcode 专栏

[中等] 147. 对链表进行插入排序

[中等] 147. 对链表进行插入排序

题目

解法

常规解法

数组解法