题目描述
给你链表的头结点 head，请将其按 升序 排列并返回 排序后的链表。
进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
示例 1：
输入：head = [4,2,1,3]
输出：[1,2,3,4]
示例 2：
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
示例 3：
输入：head = []
输出：[]
思路&js代码
1、自顶向下归并排序
- 找到链表的中点，以中点为分界，将链表拆分成两个子链表。寻找链表的中点可以使用快慢指针的做法，快指针每次移动 2 步，慢指针每次移动 1 步，当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中点。
- 对两个子链表分别排序。
- 将两个排序后的子链表合并，得到完整的排序后的链表。可以使用「21. 合并两个有序链表」的做法，将两个有序的子链表进行合并。
上述过程可以通过递归实现。递归的终止条件是链表的节点个数小于或等于 1，即当链表为空或者链表只包含 1 个节点时，不需要对链表进行拆分和排序。
// 递归实现合并两个链表
var mergeTwoLists = function (l1, l2) {
if (l1 === null) {
return l2
} else if (l2 === null) {
return l1
} else if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2)
return l1
} else {
l2.next = mergeTwoLists(l1, l2.next)
return l2
}
}
// 排序
const toSortList = (head, tail) => {
if (head === null) {
return head;
}
if (head.next === tail) {
head.next = null;
return head;
}
let slow = head, fast = head;
while (fast !== tail) {
slow = slow.next;
fast = fast.next;
if (fast !== tail) {
fast = fast.next;
}
}
const mid = slow;
return mergeTwoLists(toSortList(head, mid), toSortList(mid, tail));
}
var sortList = function(head) {
return toSortList(head, null);
};