python 链表归并排序

链表归并排序是一种常见的排序算法，用于对链表进行排序。下面是一个 Python 实现的链表归并排序的示例代码：

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

def merge_sort(head):
    if not head or not head.next:
        return head
    
    # 找到链表中点
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    
    right_head = slow.next
    slow.next = None
    
    # 递归地对子链表进行归并排序
    left_sorted = merge_sort(head)
    right_sorted = merge_sort(right_head)
    
    # 合并两个有序链表
    dummy = ListNode(0)
    curr = dummy
    while left_sorted and right_sorted:
        if left_sorted.val < right_sorted.val:
            curr.next = left_sorted
            left_sorted = left_sorted.next
        else:
            curr.next = right_sorted
            right_sorted = right_sorted.next
        curr = curr.next
    
    if left_sorted:
        curr.next = left_sorted
    else:
        curr.next = right_sorted
    
    return dummy.next

这个示例代码中，我们定义了一个 `ListNode` 类来表示链表节点。`merge_sort` 函数使用递归的方式实现了链表归并排序。首先找到链表的中点，然后将链表切分为两个子链表，分别对两个子链表进行归并排序，最后合并两个有序子链表并返回结果。

你可以使用以下代码测试上述实现：

# 创建链表
head = ListNode(4)
node1 = ListNode(2)
node2 = ListNode(1)
node3 = ListNode(3)
head.next = node1
node1.next = node2
node2.next = node3

# 打印排序前的链表
curr = head
while curr:
    print(curr.val, end=" ")
    curr = curr.next

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

# 打印排序后的链表
print("\nSorted list:")
curr = sorted_head
while curr:
    print(curr.val, end=" ")
    curr = curr.next

以上代码首先创建了一个包含 4、2、1、3 的链表，然后对链表进行归并排序，并打印排序前后的链表结果。

希望能对你有所帮助！如果有任何问题，请随时提问。