148. 链表排序

1. 题目描述

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:

输入: 4->2->1->3
输出: 1->2->3->4

示例 2:

输入: -1->5->3->4->0
输出: -1->0->3->4->5

2. 解题思路

（1）归并排序：
题目要求在O(n log n) 时间复杂度和常数级空间复杂度下对链表进行排序，恰好归并排序可以满足要求。

其主要思路如下：

• 先判断链表是否只有一个元素，若是则直接返回
• 使用快慢指针，找到链表的中间节点
• 对链表的前半部分和后半部分分别递归的进行归并排序
• 最后将两个子链表进行合并

（2）借助数组来实现：
我们可以借助数组来实现这个题目，将链表转化为数组，对数组的元素进行排序。排序完成之后，将数组再转化为链表。
不过这种方法空间复杂度为O(n)

3. 代码实现

归并排序：

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var sortList = function(head) {
    // 若为空链表或只有一个节点，就直接返回
    if(head === null || head.next === null){
        return head
    }
    // 使用快慢指针获取链表的中间值
    let fast = head
    let slow = head
    while(slow.next && fast.next && fast.next.next){
        slow = slow.next
        fast = fast.next.next
    }
    // 将链表分成两个
    const middle = slow.next
    slow.next = null
    // 对左右的两个链表分别递归的进行归并排序
    const left = head
    const right = middle
    return merge(sortList(left), sortList(right))
};
function merge (left, right) {
    // 初始化一个空的结果节点
    let res = new ListNode(null);
    // 当前节点
    let prev = res;   
    while (left && right) {
        // 如果左边的值小于右边的值，当前节点指向左节点，左节点指向下一个节点
        if (left.val < right.val) {
            [prev.next, left] = [left, left.next]
        }else {
        // 如果右边的值小于左边的值，当前节点指向右节点，右节点指向下一个节点
            [prev.next, right] = [right, right.next];
        }
        // 当前节点指向下一个节点
        prev = prev.next;
    }
    // 如果还有剩余的节点，就直接拼接在结果链表的最后
    prev.next = left ? left : right;
    return res.next;
}

数组实现：

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var sortList = function(head) {
    if(head === null || head.next === null){
        return head
    }
    let cur = head
    let index = 0
    const arr = []
    // 将链表转化为数组
    while(cur){
        arr[index] = cur.val
        cur = cur.next
        index ++
    }
    // 对数组进行排序
    arr.sort((a,b) => a-b)
    // 将数组转化为链表
    cur = head
    index = 0
    while(cur){
        cur.val = arr[index]
        index ++
        cur = cur.next
    }
    return head
};

4. 提交结果

归并排序：

数组实现：