<jupyter_start><jupyter_text>说明：    以 O(nlog(n)) 的 时间复杂度排序Example 1:    Input: 4->2->1->3    Output: 1->2->3->4    Example 2:    Input: -1->5->3->4->0    Output: -1->0->3->4->5<jupyter_code>class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
# 归并排序
class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        p, q = head, head.next
        while q and q.next:
            p = p.next
            q = q.next.next
        mid = p.next # mid为head中间部分之后的半段
        p.next = None # head变成了只有中间的的前半段
        l, r = self.sortList(head), self.sortList(mid)
        dummy = res = ListNode(-float('inf'))
        while l and r:
            if l.val > r.val:
                dummy.next = l
                l = l.next
            else:
                dummy.next = r
                r = r.next
            dummy = dummy.next
        dummy.next = l if l else r
        return res.next
class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        p, q = head, head.next
        while q and q.next:
            p = p.next 
            q = q.next
        mid = p
        p.next = None
        l, r = self.sortList(head), self.sortList(mid)
        dummy = res = ListNode(-float('inf'))
        while l and r:
            if l.val < r.val:
                res.next = l
                l = l.next
            else:
                res.next = r
                r = r.next
            res = res.next
        res.next = l if l else r
        return dummy.next<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.11217183770883055, 'fraction_numerical': 0.012529832935560859, 'mean_word_length': 1.2972602739726027, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 22, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '314137', 'license': 'Apache-2.0', 'n_tokens_mistral': 574, 'n_tokens_neox': 569, 'n_words': 156, 'path': 'Linked List/0902/148. Sort List.ipynb', 'repo_name': 'YuHe0108/Leetcode', 'size': '1676'}