leetcode 077. 链表排序 JavaScript

//  剑指 Offer II 077. 链表排序
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var sortList = function (head) {
    // 1. 首先判断当前链表不存在 ，或链表只有一个节点，则直接返回 head
    if (!head || !head.next) {
        return head;
    }
    // 2. 获取分割的右侧链表
    let rightLists = split(head);
    // 3. 获取分割的左侧链表, 当获取到右侧链表后，会将链表断开，从而剩余 head 为 左侧链表
    let leftLists = head;
    // 4. 返回合并并排序后的链表
    return mergeList(sortList(leftLists), sortList(rightLists));
};
// 排序并合并左右链表
function mergeList(leftLists, rightLists) {
    // 创建一个空的链表
    let res = new ListNode();
    // 复制一份当前空的链表
    let temp = res;
    // 判断左侧链表存在，且左右链表也存在
    while (leftLists !== null && rightLists !== null) {
        // 如果左侧链表值小于右侧链表值
        if (leftLists.val <= rightLists.val) {
            // 将空链表的下一个节点指向值小的链
            res.next = leftLists;
            // 左侧链表指针向后移动一位，继续遍历
            leftLists = leftLists.next;
        } else if (leftLists.val > rightLists.val) {
            // 否则当右侧链表节点值小，同理，将小值赋值给 res
            res.next = rightLists;
            // 右侧链表指针后移一位
            rightLists = rightLists.next;
        }
        // 同时，每次循环，将新创建的链表的指针后移一位，为了连接下一个节点
        res = res.next;
    }
    // 如果循环结束，左侧链表不为 null，说明左侧链表有剩余，拼接左侧链表
    if (leftLists !== null) {
        res.next = leftLists;
    }
    // 如果循环结束，右侧链表不为 null，说明右侧链表有剩余，拼接右侧链表
    if (rightLists !== null) {
        res.next = rightLists;
    }
    // 返回创建链表的 next，因为第一个节点没有值
    return temp.next;
}
// 分割链表为左右链表
function split(head) {
    // 使用快慢指针循环
    let slow = head;
    let fast = head.next;
    // 当快指针指向最后一个节点时，慢指针刚好指向中间的节点
    while (fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    // 断开 head 指针下一个节点
    let lists = slow.next;
    slow.next = null;
    // 返回慢指针指向的节点的下一个，即为分割后的右侧链表
    return lists;
}