题目如下：
本体可以直接使用简介形解法：
# 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: #主要是要看怎么在常数级的时间复杂度下实现，只能用一个变量，太奇怪了 #可以使用归并排序 ls=[] while head: ls.append(head.val) head=head.next ls=sorted(ls) node=ListNode(0) cur=node for i in ls: node.next=ListNode(i) node=node.next return cur.next
方法二：
使用归并排序，时间复杂度在O(nlogn)内：
也就是自顶向下归并排序
对链表自顶向下归并排序的过程如下。
找到链表的中点，以中点为分界，将链表拆分成两个子链表。寻找链表的中点可以使用快慢指针的做法，快指针每次移动 22 步，慢指针每次移动 11 步，当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中点。
对两个子链表分别排序。
将两个排序后的子链表合并，得到完整的排序后的链表。可以使用「21. 合并两个有序链表」的做法，将两个有序的子链表进行合并。
上述过程可以通过递归实现。递归的终止条件是链表的节点个数小于或等于 11，即当链表为空或者链表只包含 11 个节点时，不需要对链表进行拆分和排序。
class Solution: def sortList(self, head: ListNode) -> ListNode: def sortFunc(head: ListNode, tail: ListNode) -> ListNode: if not head: return head if head.next == tail: head.next = None return head slow = fast = head while fast != tail: slow = slow.next fast = fast.next if fast != tail: fast = fast.next mid = slow return merge(sortFunc(head, mid), sortFunc(mid, tail)) def merge(head1: ListNode, head2: ListNode) -> ListNode: dummyHead = ListNode(0) temp, temp1, temp2 = dummyHead, head1, head2 while temp1 and temp2: if temp1.val <= temp2.val: temp.next = temp1 temp1 = temp1.next else: temp.next = temp2