在用户输入后使用快速排序对单个链表进行排序，然后插入新节点和重新排序列表

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

def quicksort(head):
    if not head or not head.next:
        return head
    
    # 选择基准节点
    pivot = head
    head = head.next
    
    # 分割链表
    smaller = ListNode()
    larger = ListNode()
    smaller_tail = smaller
    larger_tail = larger
    
    while head:
        if head.val < pivot.val:
            smaller_tail.next = head
            smaller_tail = smaller_tail.next
        else:
            larger_tail.next = head
            larger_tail = larger_tail.next
        head = head.next
    
    smaller_tail.next = None
    larger_tail.next = None
    
    # 递归排序
    smaller = quicksort(smaller.next)
    larger = quicksort(larger.next)
    
    # 连接链表
    if smaller:
        smaller_tail = smaller
        while smaller_tail.next:
            smaller_tail = smaller_tail.next
        smaller_tail.next = pivot
        pivot.next = larger
        return smaller
    else:
        pivot.next = larger
        return pivot

# 创建链表
def createLinkedList(nums):
    head = ListNode()
    tail = head
    for num in nums:
        tail.next = ListNode(num)
        tail = tail.next
    return head.next

# 打印链表
def printLinkedList(head):
    while head:
        print(head.val, end=" ")
        head = head.next
    print()

# 测试
nums = [4, 2, 1, 3, 5]
head = createLinkedList(nums)
print("原始链表：")
printLinkedList(head)

sorted_head = quicksort(head)
print("排序后的链表：")
printLinkedList(sorted_head)

def insertNode(head, val):
    new_node = ListNode(val)
    
    # 找到插入位置的前一个节点
    prev = None
    curr = head
    while curr and curr.val < val:
        prev = curr
        curr = curr.next
    
    # 插入新节点
    new_node.next = curr
    if prev:
        prev.next = new_node
    else:
        head = new_node
    
    return head

# 创建链表
nums = [1, 2, 4, 5]
head = createLinkedList(nums)
print("原始链表：")
printLinkedList(head)

# 插入新节点
val = 3
head = insertNode(head, val)
print("插入新节点后的链表：")
printLinkedList(head)

# 重新排序链表
sorted_head = quicksort(head)
print("重新排序后的链表：")
printLinkedList(sorted_head)