给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
进阶：
你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
插入排序的时间复杂度是$O(n^2)$
$O(n;log(n))$的时间复杂度算法有归并排序，堆排序和快速排序
其中最适合链表的排序算法是归并排序。
示例：
1 2 3 4 5 6 7 8 输入：head = [4,2,1,3] 输出：[1,2,3,4] 输入：head = [-1,5,3,4,0] 输出：[-1,0,3,4,5] 输入：head = [] 输出：[]
题解： 解法一：通过新建列表 超时
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 class Solution : def sortList (self, head: ListNode ) -> ListNode: dummy = ListNode(val=float ("-inf" ),next =head) res = ListNode(0 ) pre = dummy while pre and pre.next : pre = dummy cur = pre.next while pre.next .next != None : if cur.val > cur.next .val: pre.next = cur.next cur.next = cur.next .next pre.next .next = cur cur = pre.next .next pre = pre.next continue pre = pre.next cur = cur.next pre.next .next = res.next res.next = pre.next pre.next = None pre = dummy return res.next
官方题解：自顶向下归并排序 对链表自顶向下归并排序的过程如下。
找到链表的中点，以中点为分界，将链表拆分成两个子链表。寻找链表的中点可以使用快慢指针的做法，快指针每次移动 2 步，慢指针每次移动 1 步，当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中点。
对两个子链表分别排序。
将两个排序后的子链表合并，得到完整的排序后的链表。可以使用「21. 合并两个有序链表 」的做法，将两个有序的子链表进行合并。
上述过程可以通过递归实现。递归的终止条件是链表的节点个数小于或等于 11，即当链表为空或者链表只包含 1 个节点时，不需要对链表进行拆分和排序。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 class Solution : def sortFunc (self,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 self.merge(self.sortFunc(head, mid), self.sortFunc(mid, tail)) def merge (self,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 temp2 = temp2.next temp = temp.next if temp1: temp.next = temp1 elif temp2: temp.next = temp2 return dummyHead.next def sortList (self, head: ListNode ) -> ListNode: return self.sortFunc(head, None )
官方题解：自底向上 使用自底向上的方法实现归并排序，则可以达到 $O(1)$ 的空间复杂度。
首先求得链表的长度$length$，然后将链表拆分成子链表进行合并。
具体做法如下。
使用$subLength$表示每次需要排序的子链表的长度，初始时$subLength=1$。
每次将链表拆分成若干个长度为$subLength$的子链表（最后一个子链表的长度可以小于$subLength$），按照每两个子链表一组进行合并，合并后即可得到若干个长度为$subLength \times 2$的有序子链表（最后一个子链表的长度可以小于$subLength \times 2$）。合并两个子链表仍然使用「21. 合并两个有序链表 」的做法。
将$subLength$的值加倍，重复第2步，对更长的子链表进行合并操作，直到有序子链表的长度大于或等于 $length$，整个链表排序完毕。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 def sortList (self, head: ListNode ) -> ListNode: if not head: return head length = 0 node = head while node: length += 1 node = node.next dummyHead = ListNode(0 , head) subLength = 1 while subLength < length: prev, curr = dummyHead, dummyHead.next while curr: head1 = curr for i in range (1 , subLength): if curr.next : curr = curr.next else : break head2 = curr.next curr.next = None curr = head2 for i in range (1 , subLength): if curr and curr.next : curr = curr.next else : break succ = None if curr: succ = curr.next curr.next = None merged = self.merge(head1, head2) prev.next = merged while prev.next : prev = prev.next curr = succ subLength <<= 1 return dummyHead.next
