单链表的合并排序代码事例

单链表的合并排序通过递归将两个已排序的链表合并成一个新的有序链表。这里是一个基于Python的简单代码示例：

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

def merge_sort_linked_list(head):
    if not head or not head.next:
        return head
    
    # 分割链表
    middle = get_middle_node(head)
    second_half = middle.next
    middle.next = None
    
    # 对两半分别进行排序
    first_half = merge_sort_linked_list(head)
    second_half = merge_sort_linked_list(second_half)
    
    # 合并两个排序好的链表
    return merge_sorted_lists(first_half, second_half)

def get_middle_node(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

def merge_sorted_lists(l1, l2):
    dummy = ListNode()
    current = dummy

    while l1 is not None and l2 is not None:
        if l1.val < l2.val:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next

    if l1 is not None:
        current.next = l1
    elif l2 is not None:
        current.next = l2

    return dummy.next

# 使用示例
head = ListNode(4, ListNode(2, ListNode(1)))
sorted_head = merge_sort_linked_list(head)

这个代码首先定义了一个`ListNode`类表示链表节点，并实现了一个`merge_sort_linked_list`函数，它会递归地分割和合并链表。`get_middle_node`函数用于找到中间节点，以便平均分治。最后，`merge_sorted_lists`函数负责合并两个已经排序的链表。