对链表进行插入排序 _插入排序

对链表进行插入排序
给定单个链表的头head，使用插入排序对链表进行排序，并返回排序后链表的头。
插入排序算法的步骤:
插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。重复直到所有输入数据插入完为止。
下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时，从输入数据中删除一个元素(红色)，并就地插入已排序的列表中。
对链表进行插入排序。
示例 1：
输入: head = [4,2,1,3]输出: [1,2,3,4]
示例2：
输入: head = [-1,5,3,4,0]输出: [-1,0,3,4,5]
关键词1：插入排序
遍历数组，把遍历到的数字插入到有序序列的合适位置，形成一个新的有序序列
关键词2：链表
任务：
对链表做插入排序
任务1：遍历链表
任务2：找到合适的位置，插入节点
任务1：
遍历链表。只需要一个cur指针，指向有序序列之后的第一个节点，将该节点插入到合适位置后，指针后移一位。直至遍历到空节点。
同时，维护一个last指针，指向有序序列的最后一个数字。
当然，最好设置一个空的头结点dinny 。避免，在节点v需要插入到头结点head之前的时候，做多余的处理。
dinny=ListNode()dinny.next=headlast = head #有序序列的最后一个cur = last.next#待排序的第一个
【对链表进行插入排序】任务2：
寻找合适的位置，进行插入
对于数组来说，因为有随机访问的特点，可以从后往前遍历，找到一个适合节点v的位置。但是单链表只能从前往后遍历，找到第一个大于节点v的节点m，并将节点v插入到节点m之前。
寻找节点v的合适位置的步骤如下：
1、设置一个用于判断大小的临时指针，该指针指向头结点
2、比较的下一个节点和v的大小
3、如果的下一个节点小，说明节点v要插到节点的下一个节点的后边位置，指针后移，直至找到的下一个节点的值大于v的值；如果v的小，说明找到了第一个比v大的节点，将v插在该节点的前面。该位置是节点的后边和节点的下一个节点的前面。
至于为什么比较的下一个节点和v的大小，而不是直接比较v和节点的大小。是因为，在单链表中插入链表要知道其前一个节点，如果直接比较的话，需要重新寻找节点的前一个节点。当然可以在设置一个指针，指向的前一个节点。但是太麻烦了，还不如用的下一个节点作比较。
在遇到cur和last已经处于一个有序的情况下，只需要将last和cur后移一格位置即可。这样可以，减少从头遍历链表，以寻找合适位置的时间。
if cur.val>=last.val:last=curcur=last.next
以下是完整的代码：
class Solution:def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:dinny=ListNode()#设置一个空的头结点dinny.next=headlast = head #有序序列的最后一个cur = last.next#待排序的第一个while cur :if cur.val>=last.val:last=curcur=last.nextelse:comparetemp=dinny #插入时的临时节点,用来做判断while cur.val>=comparetemp.next.val and comparetemp.next != cur:comparetemp=comparetemp.next#找到合适的位置了，开始插入last.next=cur.nextcur.next=comparetemp.nextcomparetemp.next=curcur = last.nextreturn dinny.next
打家劫舍