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

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

对链表进行插入排序。

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

插入排序算法：

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

示例 1：

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

示例 2：

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

通过次数33,847 | 提交次数52,419

Second Try

2020-07-09

优化版本的冒泡排序，题解都是这个思路。看是否不需要排序，找到第一个需要排序的点，该点比前一个点小，把该点抽离出来，从开头遍历下去，找到可以插入的位置，也即前后点分别比该点小和大。其实这个复杂度，也是O(n^2)才对，只是能够很好的利用已经排序好的内容，是一个比较小的O(n^2)。如果链表已经有序，只需要O(n)的复杂度。

其实First Try里的才是正规的冒泡排序，每次找出剩下的部分最小的，然后放上去。奈何找出最小的这部分太耗费时间了，每次都遍历后面的一次，并不能利用已经有的局部排序。就算已经是有序版本，依然需要O(n^2)的复杂度。

class Solution(object):
    def insertionSortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        dummy = ListNode(None)
        dummy.next = head
        pre = dummy 
        curr = head 
        while curr:
            # print(curr.val, dummy.next )
            if pre.val <= curr.val:
                pre, curr = curr, curr.next  
            else:
                # 查找一个适合把当前比较小的node放进来的位置
                t = dummy  # 就算curr需要排在第一位，，也不影响原来列表的dummy
                # 一直找到第一个比curr大的值，那么前一个就比curr小
                while t.next.val < curr.val:
                    t = t.next 
                # print(t.val, t.next.val)
                downstream = t.next # t.next比curr大
                t.next = curr # t比curr小
                downstreamII = curr.next 
                curr.next = downstream
                # 处理pre继续循环的部分，pre还是不变，但是curr变成了之前的curr的下一个参数了       
                curr = downstreamII
                pre.next = curr  # 没有这个直接又是一个错误的无限循环

        return  dummy.next 

执行用时：136 ms, 在所有 Python 提交中击败了93.11%的用户
内存消耗：16.5 MB, 在所有 Python 提交中击败了100.00%的用户

First Try

2020-07-07

插入排序算法总归是比较慢的，为了改变位置需要记录最小值的前一个点，为了把最小值往前方也需要记录上一个已经排序好的位置。然后就是在各种边界条件中一点点试出来思路清晰的写法，比如是否要用dummy, left, node, mini, premini, 循环的时候是用node还是node.next之类。

感觉已经是比较标准的插入排序算法了，结果时间竟然这么后，可能别人用列表了吧。。。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def insertionSortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        dummy = ListNode(None)
        dummy.next = head

        left =  dummy 
        while left.next:
            premini = node = left 
            mini = left.next 
            while node.next:
                if node.next.val < mini.val:
                    premini = node
                    mini = node.next  
                node = node.next 
            premini.next = mini.next 
            mini.next = left.next 
            left.next = mini
            left = mini 

        return dummy.next 

执行用时：3588 ms, 在所有 Python 提交中击败了5.05%的用户
内存消耗：16.1 MB, 在所有 Python 提交中击败了100.00%的用户