LeetCode刷题笔记第148题：排序链表

想法：
通过归并排序完成对链表中元素的重排，并完成链表的升序排序输出

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 先使用归并排序，再构建升序链表

        # 链表中仅有一个元素或没有元素直接返回
        if not head or not head.next:
            return head 

        # 快慢指针找到链表中中间结点
        slow, fast = head, head.next
        while fast and fast.next:
            fast, slow = fast.next.next, slow.next
        mid, slow.next = slow.next, None

        # 归并排序后的左右两部分
        left, right = self.sortList(head), self.sortList(mid)


        # 遍历左右两部分将较小元素先入链表
        h = res = ListNode(0)
        while left and right:
            if left.val <= right.val:
                h.next,left = left, left.next
            else:
                h.next,right = right, right.next
            h = h.next
        h.next = left if left else right

        return res.next