插入排序对单链表排序

插入排序是一种简单直观的排序算法，对于单链表的排序也可以采用插入排序。具体实现方法如下：
1. 将单链表的表头分离，形成两个表，一个有序表（La1），一个无序表（La2）。
2. 对无序表进行循环，将每个元素插入到有序表中，使得有序表仍然有序。
3. 最终得到的有序表即为排好序的单链表。

下面是Python代码实现：

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

def insertionSortList(head: ListNode) -> ListNode:
    if not head or not head.next:
        return head
    dummy = ListNode(0)
    dummy.next = head
    last_sorted = head
    curr = head.next
    while curr:
        if last_sorted.val <= curr.val:
            last_sorted = last_sorted.next
        else:
            prev = dummy
            while prev.next.val <= curr.val:
                prev = prev.next
            last_sorted.next = curr.next
            curr.next = prev.next
            prev.next = curr
        curr = last_sorted.next
    return dummy.next