在python中使用插入排序对单链表进行排序

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

def insertionSort(head):
    if head is None or head.next is None:
        return head

    dummy = Node(0)  # 创建一个虚拟头节点
    dummy.next = head

    current = head.next  # 从链表的第二个节点开始
    head.next = None  # 将链表拆分为已排序部分和未排序部分

    while current:
        prev = dummy
        next_node = current.next

        # 在已排序部分中找到合适的位置插入当前节点
        while prev.next and prev.next.value < current.value:
            prev = prev.next

        # 插入当前节点
        current.next = prev.next
        prev.next = current

        current = next_node

    return dummy.next

# 创建一个示例链表
head = Node(3)
node1 = Node(1)
node2 = Node(4)
node3 = Node(2)

head.next = node1
node1.next = node2
node2.next = node3

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

# 打印排序后的链表
while sorted_head:
    print(sorted_head.value)
    sorted_head = sorted_head.next