链表合并排序的实现

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

def merge(left, right):
    dummy = ListNode(0)  # 创建一个哑节点作为合并后链表的头节点
    cur = dummy  # 创建一个指针指向当前节点
    while left and right:
        if left.val < right.val:
            cur.next = left
            left = left.next
        else:
            cur.next = right
            right = right.next
        cur = cur.next
    if left:
        cur.next = left
    if right:
        cur.next = right
    return dummy.next

def merge_sort(head):
    if not head or not head.next:
        return head
    
    slow = head
    fast = head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    
    right = merge_sort(slow.next)  # 递归排序右半部分链表
    slow.next = None  # 断开链表，将链表一分为二
    left = merge_sort(head)  # 递归排序左半部分链表

    return merge(left, right)  # 合并左右两部分链表

# 测试用例
# 创建链表1->4->3->2->5
head = ListNode(1)
head.next = ListNode(4)
head.next.next = ListNode(3)
head.next.next.next = ListNode(2)
head.next.next.next.next = ListNode(5)

# 对链表进行合并排序
sorted_head = merge_sort(head)

# 输出排序后的链表
while sorted_head:
    print(sorted_head.val, end=" ")
    sorted_head = sorted_head.next