设待排序的记录序列用单链表作存储结构，编写直接插入排序

算法的代码。

好的，以下是单链表直接插入排序算法的代码：

# 定义链表节点类
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def insertionSortList(head: ListNode) -> ListNode:
    if not head or not head.next:
        return head
    dummy = ListNode(0)     # 定义新的链表节点
    dummy.next = head       # 新链表的头结点是原链表的第一个节点
    lastSorted = head       # 上一个已排序的节点
    curr = head.next        # 当前待排序节点
    while curr:
        # 单链表中删除待排序的节点
        if lastSorted.val <= curr.val:
            lastSorted = lastSorted.next
        else:
            prev = dummy
            while prev.next.val <= curr.val:
                prev = prev.next
            lastSorted.next = curr.next
            curr.next = prev.next
            prev.next = curr
        curr = lastSorted.next
    return dummy.next

该算法的时间复杂度为 O(n^2)，空间复杂度为 O(1)。