题目 148. 排序链表
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
示例 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 * 104]内 -105 <= Node.val <= 105
进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
解法一 归并排序 （辅助链表）
归并排序（Merge Sort）是运用分治法的排序算法。
归并排序的核心算法是归并算法，用于将两个有序的数组组合成一个有序的数组。步骤：
- 初始化两个指针，分别指向两个有序数组的起始位置。
- 比较两个指针所指的元素，将较小的元素加入结果数组，并移动对应的指针。
- 重复这个过程，直到某一个数组的所有元素都被合并。
- 将剩余数组的元素直接添加到结果数组中，因为剩下的部分已经是有序的。
可以看出这种有序合并算法需要额外的数组空间——一个结果数组。
时间复杂度为 O(n1 + n2), 空间复杂度为 O(n1 + n2)
归并排序利用分治法，将要排序的数组分成较小的两个子数组分别排序（用递归），然后再将排序好的子数组合并成一个有序的大数组。具体排序示例如下：
class Solution {
// 归并排序
public ListNode sortList(ListNode head) {
// 结束条件
if (head == null || head.next == null) return head;
// 从中间裁链
ListNode slow = head, fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode temp = slow.next;
slow.next = null;
ListNode right = sortList(temp), left = sortList(head);
ListNode signNode = new ListNode(0), preResult = signNode;
while (left != null || right != null) {
if (left.val > right.val) {
signNode.next = new ListNode(right.val);
right = right.next;
} else {
signNode.next = new ListNode(left.val);
left = left.next;
}
signNode = signNode.next;
}
signNode.next = left != null ? left : right;
return preResult.next;
}
}时间复杂度：O(nlogn)
空间复杂度：O(nlogn)，因为需要 logn 层递归，每层递归需要长度为 n 的辅助链表。如果要 O(1) 级别的空间复杂度，就不能用归并排序。
解法二（改进） 不用辅助链表，而是在原本链表上合并
思路与解法一一致，区别只是在不借助辅助链表，而是直接在原链表上合并，将空间复杂度降为O(1)。
class Solution {
// 归并排序
public ListNode sortList(ListNode head) {
// 结束条件
if (head == null || head.next == null) return head;
// 从中间裁链
ListNode slow = head, fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode temp = slow.next;
slow.next = null;
ListNode right = sortList(temp), left = sortList(head), signNode, resultNode;
if (left.val > right.val) {
signNode = left.val > right.val ? right : left;
resultNode = left.val > right.val ? right : left;
right = right.next;
} else {
signNode = left;
resultNode = left;
left = left.next;
}
while (left != null && right != null) {
if (left.val > right.val) {
signNode.next = right;
signNode = signNode.next;
right = right.next;
} else {
signNode.next = left;
signNode = signNode.next;
left = left.next;
}
signNode.next = null;
}
signNode.next = left != null ? left : right;
return resultNode;
}
}
小结
通过今天的题目学习了归并排序，要求O(nlogn)的时间复杂度，可以联想到和树结构有关，而树结构大多与“二分”、“分治”的思想有关，自然联想到分治排序的代表——归并排序！这种分治也是递归法的的一大用武之地！