思路：

• 参考yxc大佬

不能用自上而下的归并排序，因为这样会用到o(logn)的空间
只能使用自底向上的归并排序，只用o(1)空间

自底向上的归并排序

1、先把链表分成若干个相连的节点对，也就是从头节点开始两个两个为一对，进行内部排序
2、再把四个四个节点在内部排序，。。。，最后把整个链表排序，进行o(logn)层排序

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        dummy = ListNode(-1)
        dummy.next = head
        # 求链表长度
        n = 0 
        p = head
        while p:
            n += 1
            p = p.next

        i = 1
        while i < n: # 每一段有多少个数
            cur = dummy
            # j枚举每一段,每一段有i个数
            j = 0
            while j + i < n: # j表示二路归并的起点
                left = cur.next; right = cur.next # left.,right表示相邻段的各自最左（开始）的节点
                for k in range(0, i):
                    right = right.next # 使右指针指向下一段的最左的节点

                l = 0; r = 0 # l,r 表示二路归并的相邻两段的索引，都从0到i-1
                while l < i and r < i and right: 
                    # right不为空，因为有可能合并完左边后，右边不够长（总数为奇数个的话会少一个不够合并）
                    # 归并过程，哪一段的开头元素小就先连起该元素,cur代表新链表的当前节点
                    if left.val <= right.val: 
                    # 当左边一段开头元素小于右边段开头元素，cur下一个连上左开头元素
                        cur.next = left
                        cur = left
                        left = left.next
                        l += 1
                    else:
                        cur.next = right
                        cur = right
                        right = right.next
                        r += 1
                while l < i: # 可能有些段还没被合并
                        cur.next = left
                        cur = left
                        left = left.next
                        l += 1
                while r < i and right: # 注意凡是合并右边段，都需要判断右指针是否指向空节点
                        cur.next = right
                        cur = right
                        right = right.next
                        r += 1
                # right 最后是下一相邻两段的第一段的开头节点（若存在）
                cur.next = right 
                # 每合并完相邻两段，就要把cur.next更新到下一段的开头节点（right也有可能为空节点，此时cur就是尾节点）

                j += i*2

            i *= 2
        return dummy.next