✅148. 排序链表

[Ray-56]

148. 排序链表

给你链表的头结点 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 = []
输出：[]

[Ray-56]

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var sortList = function(head) {
    const dummy = new ListNode();
    dummy.next = head;

    let fast = dummy;
    let slow = dummy;
    while (fast.next) {
        fast = fast.next;
        slow = slow.next;
        if (fast.next) {
            fast = fast.next;
        }
    }

    if (slow === fast) return dummy.next;
    const right = slow.next;
    slow.next = null;
    const left = dummy;
    return merge(sortList(left.next), sortList(right));
};

function merge(leftList, rightList) {
    const dummy = new ListNode();
    dummy.next = leftList;
    let lNode = dummy;
    let rNode = rightList;

    while (lNode && rNode) {
        while (lNode.next && lNode.next.val < rNode.val) {
            lNode = lNode.next;
        }
        const next = rNode.next;
        rNode.next = lNode.next;
        lNode.next = rNode;
        rNode = next;
    }
    return dummy.next;
}