写一个函数，实现链表的排序（使链表中元素的从无序到有序，要求从小到大），使用插入排序

插入排序是一种简单直观的排序算法，它的工作原理类似于构建一个有序序列的过程。对于链表的插入排序，我们可以按照以下步骤编写一个函数：

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

def insertion_sort_linked_list(head):
    if not head or not head.next:
        return head  # 如果链表为空或只有一个节点，无需排序

    # 初始化一个空的已排序链表和一个指针
    sorted_head = None
    current = head

    while current:
        # 插入当前节点到已排序链表中的适当位置
        if not sorted_head or current.val < sorted_head.val:
            current.next = sorted_head
            sorted_head = current
        else:
            prev = sorted_head
            while prev.next and prev.next.val < current.val:
                prev = prev.next
            current.next = prev.next
            prev.next = current

        # 移动到下一个未排序节点
        current = current.next

    return sorted_head

# 示例
# 创建一个无序链表
head = ListNode(4)
head.next = ListNode(2)
head.next.next = ListNode(1)
head.next.next.next = ListNode(3)

# 调用函数对链表进行插入排序
sorted_head = insertion_sort_linked_list(head)

在这个函数中，我们遍历链表，每次将当前节点插入到已排序部分的正确位置。注意这里假设输入链表包含非负整数。