topic148

排序链表

1. 题目描述

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

2. 示例

示例1

输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例2

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例3

输入：head = []
输出：[]

提示

• 链表中节点的数目在范围 $[0, 5 * 10^4]$ 内
• $-10^5 \le Node.val \le 10^5$

3. 解题

• 正常的排序需要$O(n^2)$的时间复杂度，要想实现$O(nlogn)$或$O(n)$的时间复杂度，就需要以空间换时间。

• 对于$O(nlogn)$的实现，可以先将链表所有元素提取出来，然后使用快排排序后再重新赋值。 除此之外，还可以使用归并排序，归并排序的过程如下：

  1. 找到链表的中点，以中点为分界，将链表拆分成两个子链表。寻找链表的中点可以使用快慢指针的做法，快指针每次移动 2 步，慢指针每次移动 1 步，当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中点。

  2. 对两个子链表分别排序。

  3. 将两个排序后的子链表合并，得到完整的排序后的链表。

• 已证明：基于比较的排序算法时间复杂度最小为$O(nlogn)$，因此实现算法时间复杂度小于$O(nlogn)$的排序必然以空间换时间 对于$O(n)$的时间复杂度，可以使用基于收集的算法，例如桶排序。排序完成后重新赋值。