题目

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

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

进阶：

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

示例

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

归并

作者：user7746o
链接：https://leetcode-cn.com/problems/sort-list/solution/jsjie-pai-xu-lian-biao-wen-ti-by-user7746o/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

归并排序采用了分治策略，将数组分成2个较小的数组，然后每个数组再分成两个更小的数组，直至每个数组里只包含一个元素，然后将小数组不断的合并成较大的数组，直至只剩下一个数组，就是排序完成后的数组序列。

第一步：分割

• 使用快慢指针（双指针法），获取链表的中间节点
• 根据中间节点，分割成两个小链表
• 递归执行上一步，直到小链表中只有一个节点

第二步：归并（合并有序链表）

 

let sortList = function(head) {return mergeSortRec(head)
}// 归并排序
// 若分裂后的两个链表长度不为 1，则继续分裂
// 直到分裂后的链表长度都为 1，
// 然后合并小链表
let mergeSortRec = function (head) {if(!head || !head.next) {return head}// 获取中间节点let middle = middleNode(head)// 分裂成两个链表let temp = middle.nextmiddle.next = nulllet left = head, right = temp// 继续分裂（递归分裂）left = mergeSortRec(left)right = mergeSortRec(right)// 合并两个有序链表return mergeTwoLists(left, right)
}// 获取中间节点
// - 如果链表长度为奇数，则返回中间节点
// - 如果链表长度为偶数，则有两个中间节点，这里返回第一个
let middleNode = function(head) {let fast = head, slow = headwhile(fast && fast.next && fast.next.next) {slow = slow.nextfast = fast.next.next}return slow
}// 合并两个有序链表
let mergeTwoLists = function(l1, l2) {let preHead = new ListNode(-1);let cur = preHead;while(l1 && l2){if(l1.val < l2.val){cur.next = l1;l1 = l1.next;}else{cur.next = l2;l2 = l2.next;}cur = cur.next;}cur.next = l1 || l2;return preHead.next;
}