刷题记录：单链表的排序

我第一个想法是分治
但想到分治之后就不知道该咋做了
卡了许久，遂求助官解
得“排序”二字
于是想起了合并两个排序的链表

遂得代码，如下：

class Solution:
    def sortInList(self , head: ListNode) -> ListNode:
        if not head or not head.next:       # 返回条件
            return head
        
        newHead = ListNode(-1)      # 新链表的头结点
        
        pre, slow, fast = None, head, head  # 使用快慢指针，将链表拆分
        while fast and fast.next:
            pre = slow
            slow = slow.next
            fast = fast.next.next
        pre.next = None                     # 前半链表尾结点的下一个设为 None （重要）
        
        leftList = self.sortInList(head)    # 获得排序后的两链表
        rightList = self.sortInList(slow)
        
        p = newHead                         # 对两链表进行排序并合并
        while leftList and rightList:
            if leftList.val < rightList.val:
                p.next = leftList
                leftList = leftList.next
            else:
                p.next = rightList
                rightList = rightList.next
            p = p.next
        
        if not leftList:
            p.next = rightList
        else:
            p.next = leftList
            
        return newHead.next