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 = []
输出：[]

回答：

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var sortList = function(head) {
    if (!head || !head.next) return head;
    let slow = head;
    //fast初始不设为起点，而是一个节点，可以保证中间节点位置比较均衡
    let fast = head.next;
    //快慢指针找到中间节点
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    //切断前后半部分
    let rightList = slow.next;
    slow.next = null;
    let left = sortList(head);
    let right = sortList(rightList);
    return merge(left, right)
};
//合并节点
var merge = function(left, right) {
    let dummy = new ListNode(0);
    let current = dummy;
    while (left && right) {
        if (left.val <= right.val) {
            current.next = left;
            left = left.next;
        } else {
            current.next = right;
            right = right.next;
        }
        current = current.next;
    }
    current.next = left ? left : right;
    return dummy.next;
}