单链表的插入排序python

单链表的插入排序是一种基于插入排序算法的排序方法，适用于单链表结构。下面是一个使用Python实现的单链表插入排序的示例代码：

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

def insert_sort(head):
    if not head or not head.next:
        return head
    dummy = Node(0)
    dummy.next = head
    cur = head.next
    head.next = None
    while cur:
        pre = dummy
        while pre.next and pre.next.val < cur.val:
            pre = pre.next
        temp = cur.next
        cur.next = pre.next
        pre.next = cur
        cur = temp
    return dummy.next

# 示例测试
def print_list(head):
    cur = head
    while cur:
        print(cur.val, end=" ")
        cur = cur.next
    print()

# 创建一个单链表
head = Node(4)
node1 = Node(2)
node2 = Node(1)
node3 = Node(3)
head.next = node1
node1.next = node2
node2.next = node3

print("排序前：")
print_list(head)

head = insert_sort(head)

print("排序后：")
print_list(head)