题解 | #单链表的排序# 合并递归、排序递归

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 the head node
# @return ListNode类
#
class Solution:
    # 合并两个有序链表（链表已排序）
    def merge2(self,head1,head2):
        if not head1 or not head2:
            return head2 or head1
        if head1.val>head2.val:
            head2.next=self.merge2(head1,head2.next)
            return head2
        else:
            head1.next=self.merge2(head1.next,head2)
            return head1
    # 将单个链表排序
    def sortInList(self , head: ListNode) -> ListNode:
        # write code here
        if not head or not head.next: # 链表为空或只有一个元素，直接输出链表
            return head
        left=head             # 慢指针，一次走一步
        mid=head.next         # 慢指针，一次走一步
        right=head.next.next  # 快指针，一次走两步
        while right and right.next:
            left=left.next
            mid=mid.next
            right=right.next.next
        # 此时right已移动到链表之外，mid在链表中间，left仍然在mid前一个位置
        # left mid 分开链表
        left.next=None  # 切掉left之后的元素，head变短
        return self.merge2(self.sortInList(head),self.sortInList(mid))