对链表进行直接插入排序代码

链表进行直接插入排序通常不会像数组那样直观，因为链表不像数组那样可以随机访问元素，但我们可以通过遍历整个链表的方式来实现。以下是使用Python实现的简单直接插入排序算法，适用于单向链表：

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
    
    dummy = ListNode(0)  # 创建一个虚拟头节点
    dummy.next = head
    
    current = head.next
    while current:
        key = current.val
        prev_node = dummy
        
        while prev_node.next and prev_node.next.val < key:
            prev_node = prev_node.next
        
        current.next = prev_node.next
        prev_node.next = current
        current = current.next
    
    return dummy.next  # 返回排序后的链表头

# 示例
# 假设我们有链表: [4, 2, 1, 5, 6]
# 插入排序后会变成: [1, 2, 4, 5, 6]