【前端面试常见算法题系列】148. 排序链表（中等）-一一网

“Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。”

一、题目描述

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

提示：

链表中节点的数目在范围 [0, 5 * 104] 内
-105 <= Node.val <= 105

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

二、思路分析

题目的进阶问题要求达到 O(nlogn) 的时间复杂度和 O(1) 的空间复杂度，而时间复杂度是 O(nlogn) 的排序算法包括归并排序、堆排序和快速排序（快速排序的最差时间复杂度是 O(n²)），其中最适合链表的排序算法是归并排序。

归并排序的思路分为两种，分别是自顶向下和自底向上，两种方法思考方向不太一样，但精髓都是分而治之，下面分别来探究其中的奥妙。

PS：直接上手链表可能有点混乱，我们先以数组举例，思路都是差不多的。

自顶向下

将数组分割成两半，一半为 A、一半为 B ，两半分别比较排序，但要整个数组排好序，单单 A 或 B 排好序还不够，还需要 A 和 B 再比较排序（也就是合并两个有序数组为新的有序数组，这好办，用双指针技巧嘛）。
（但是 A 或 B 要怎么排，说了这么多，不就是将长度减了而已嘛），说的没错，但如果将这个过程递归下去呢，最后是不是会变成两个长度都为 1 的元素进行比较，然后返回排完序后的结果，重复此过程，A 或 B 不就排好序了，不就可以合并了嘛。

来看看图解（图片来源于网络）：

代码实现：

function mergeSort(arr) {
    var len = arr.length;
    if(len < 2) {
        return arr;
    }
    // 比起 len/2 ，更推荐下面这种写法，可以避免数溢出
    var middle = Math.floor((right - left) / 2 + left),
        left = arr.slice(0, middle), // slice(x, y) 左闭右开，只截取 x 到 y-1 的元素
        right = arr.slice(middle);   // 截取 middle 后的所有元素
    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
    var result = [];

    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            result.push(left.shift()); // left.shift() 删除数组的第一个元素
        } else {
            result.push(right.shift());
        }
    }

    while (left.length)
        result.push(left.shift());

    while (right.length)
        result.push(right.shift());

    return result;
}
复制代码

自底向上

对数组每隔 2 个元素进行一次划分，如果数组为奇数，则最后一个元素单独划分为一组。分好组后，每个组内进行排序。根据上一步的结果，每 4 个元素划分为一组，再排序，然后每 8 个元素再划分，再排序……直到将整个数组划分为一组，就完成归并排序。

图解如下（图片来源于网络）：

大概理解了两种方法的思想后，我们要将数组换成链表来思考了。

过渡到链表

笔者使用自顶向下的方法解决这道题，来看看思路：

找到链表的中点【快慢指针解决】。
递归划分链表，直到 2 个节点一组为止。
逐步合并划分后的链表，这过程中比较排序。

三、AC 代码

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;
}

const toSortList = (head, tail) => {
    if (head === null) {
        return head;
    }
    if (head.next === tail) {
        head.next = null;
        return head;
    }
    // 找链表的中点
    let slow = head, fast = head;
    while (fast !== tail) {
        slow = slow.next;
        fast = fast.next;
        if (fast !== tail) {
            fast = fast.next;
        }
    }
    const mid = slow;
    return merge(toSortList(head, mid), toSortList(mid, tail));
}

var sortList = function(head) {
    return toSortList(head, null);
};
复制代码