排序链表

本题解采用了自底向上的归并排序算法来对链表进行排序。首先通过get_length函数计算链表的长度。然后使用迭代的方式，通过增量i（初值为1，并每次翻倍），逐步合并更长的子链表段。cut函数用于切割链表，返回后半部分的头节点，并将前半部分尾节点的next设为None，从而实现链表的分割。merge函数负责合并两个已排序的链表段。整个过程通过一个外部的while循环控制，每次循环都将链表中所有相邻的、长度为i的链表段进行合并，直到i大于或等于链表长度，此时整个链表排序完成。

时间复杂度: O(n log n)

空间复杂度: O(1)

# 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: ListNode) -> ListNode:
        if head is None or head.next is None:
            return head

        dummy = ListNode(next=head)

        def get_length(head):
            p = head
            length = 0
            while p:
                p = p.next
                length += 1
            return length

        def cut(head, n):
            p = head
            while p and n - 1 > 0:
                p = p.next
                n -= 1
            if p is None:
                return
            new_head = p.next
            p.next = None
            return new_head

        def merge(l1, l2):
            dummy = ListNode(0)
            p = dummy
            while l1 and l2:
                if l1.val < l2.val:
                    p.next = l1
                    l1 = l1.next
                else:
                    p.next = l2
                    l2 = l2.next
                p = p.next
            if l1:
                p.next = l1
            if l2:
                p.next = l2
            return dummy.next

        length = get_length(head)
        i = 1
        while i < length:
            tail = dummy
            cur = dummy.next
            while cur:
                left = cur
                right = cut(left, i)
                cur = cut(right, i)
                tail.next = merge(left, right)
                while tail.next:
                    tail = tail.next
            i *= 2
        return dummy.next