LeetCode-147-对链表进行插入排序

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

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

解题思路：

1. 首先判断head节点及其next节点是否存在，如果不存在，直接返回head；
2. 创建哑节点dummyHead=ListNode(0)，令dummyHead.next=head，目的是为了便于在head前插入节点；
3. 初始化last_sorted=head，表示已排序的末位节点，初始值为head；
4. 初始化cur=head.next，表示当前需要排序的节点，初始化为head.next；
5. 外层循环终止条件：判断cur是否存在；
6. 如果cur的val大于等于last_sorted的val，表示不需要排序；已排序的末位节点last_sorted指向cur，cur指向last_sorted.next；
7. 如果cur.val < last_sorted.val，因为插入排序需要用cur对比之前所有的值，因此需要内层循环判断，用pre指向哑节点dummyHead，如果pre.next.val<cur.val则pre前进一位，直到pre.next的值大于cur的值；
8. 例如 链表0->1->3->4->2->9，此时cur指向2，pre指向1，pre.next.val=3 > cur.val=2，此时需要将2插入到3前面；此时last_sorted指向4，表示1->3->4已经排序好了;
9. 插入2到4前面的操作：首先令last_sorted.next = cur.next，即4的后一位是9，然后cur.next = pre.next，即节点2的后面跟着节点3(pre.next)，最后令pre.next=cur，即节点1的后面跟着节点2，此时完成了2插入到3前面的操作；
10. 滑动cur指向last_sorted.next，继续下一轮外层循环；
11. 直到cur为空，结束外层循环，返回dummyHead.next。

Python3代码：

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

class Solution:
    def insertionSortList(self, head: ListNode) -> ListNode:
        if not head or not head.next: 
            return head

        dummyHead = ListNode(0)
        dummyHead.next = head

        last_sorted = head
        cur = head.next
       
        while cur:
            if cur.val >= last_sorted.val: # 不需要插入
                last_sorted = cur
                
            else:
                pre = dummyHead
                while pre.next.val < cur.val:
                    pre = pre.next
                
                last_sorted.next = cur.next
                cur.next = pre.next
                pre.next = cur
            cur = last_sorted.next
        return dummyHead.next