单链表的直接插入排序

单链表的直接插入排序（直接插入排序）是一种简单的排序算法，它通过构建有序序列逐个将未排序的元素插入到已排序的序列中。下面是单链表的直接插入排序的实现过程：

1. 创建一个新的链表，作为已排序的部分，初始为空。
2. 遍历原始链表，从第一个节点开始：
- 将当前节点从原始链表中断开，并保存下一个节点的引用。
- 在已排序的链表中找到合适的位置，将当前节点插入。
- 更新已排序链表的头节点。
- 继续处理下一个节点。
3. 返回已排序链表。

以下是单链表直接插入排序的具体实现（使用Python语言）：

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

def insert_sort_list(head):
    if not head or not head.next:
        return head

    dummy = ListNode(0)  # 创建一个虚拟头节点

    while head:
        curr = dummy
        next_node = head.next

        # 找到合适的插入位置
        while curr.next and curr.next.val < head.val:
            curr = curr.next

        # 将当前节点插入到已排序链表中
        head.next = curr.next
        curr.next = head

        # 更新已排序链表的头节点
        dummy.next = dummy.next if dummy.next else head

        # 继续处理下一个节点
        head = next_node

    return dummy.next