写一个链表的归并排序的程序

首先，定义一个函数merge，该函数将两个已排序的链表合并为一个新的已排序的链表：def merge(head1, head2): # 声明一个新的链表结点，用于保存合并后的链表
temp = None# 声明两个结点，用于遍历两个链表
p1 = head1
p2 = head2# 如果链表1和链表2均不为空时，比较两个链表的结点值，将值小的结点放入合并后的链表中
while p1 and p2:
if p1.data <= p2.data:
if temp is None:
temp = p1
else:
temp.next = p1
temp = p1
p1 = p1.next
else:
if temp is None:
temp = p2
else:
temp.next = p2
temp = p2
p2 = p2.next# 如果链表1不为空，则将剩余的链表1的结点放入合并后的链表中
if p1:
temp.next = p1 # 如果链表2不为空，则将剩余的链表2的结点放入合并后的链表中
if p2:
temp.next = p2 # 返回合并后的链表头指针
return head然后，定义一个函数mergeSort，该函数将原链表拆分为两个子链表，递归调用merge函数将子链表合并：def mergeSort(head): # 如果链表为空或只有一个结点，无需排序，直接返回
if head is None or head.next is None:
return head# 定义快慢指针，找到链表的中间结点
slow = head
fast = head # 如果快指针的下一个结点不为空，则快慢指针同时向前移动
while fast.next != None and fast.next.next != None:
slow = slow.next
fast = fast.next.next# 将链表拆分为两个链表
mid = slow.next
slow.next = None # 分别对两个链表进行排序
left = mergeSort(head)
right = mergeSort(mid)# 合并两个排序后的链表
return merge(left, right)