排序链表
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
示例 1：
codeType
输入：head = [4,2,1,3]
输出：[1,2,3,4]
示例 2：
codeType
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
示例 3：
codeType
输入：head = []
输出：[]
提示：
- 链表中节点的数目在范围 [0, 5 * 104] 内
- -105 <= Node.val <= 105
进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
解法
该解法采用分治法，自顶向上从中间一次拆分链表，直到拆分成单个节点。
合并时就会简化成对两个有序链表进行合并。
最终合并成一个有序链表。
ts
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
const merge = (head1, head2) => {
// 合并两个升序链表，穿针引线
const dummyHead = new ListNode(0);
let temp = dummyHead, temp1 = head1, temp2 = head2;
while (temp1 !== null && temp2 !== null) {
if (temp1.val <= temp2.val) {
temp.next = temp1;
temp1 = temp1.next;
} else {
temp.next = temp2;
temp2 = temp2.next;
}
temp = temp.next;
}
if (temp1 !== null) {
temp.next = temp1;
} else if (temp2 !== null) {
temp.next = temp2;
}
return dummyHead.next;
}
function sortList(head: ListNode | null): ListNode | null {
const helper = (start: ListNode | null, end: ListNode | null): ListNode | null => {
if (start === null) {
return start;
}
// 划分的链表只有一个节点，直接返回该节点
if (start.next === end) {
start.next = null;
return start;
}
// 快慢指针，快指针走两步，慢指针走一步。快指针走到尾，慢指针走到中间。
let slow = start
let fast = start
while(fast !== end){
slow = slow.next
fast = fast.next
if(fast !== end){
fast = fast.next
}
}
// 左边
const leftList = helper(start, slow)
// 右边
const rightList = helper(slow, end)
// 合并
return merge(leftList, rightList)
}
return helper(head, null)
};