148. 排序链表

题目链接

一、思想

1、排序算法选择

要求：在 O(nlogn) 时间复杂度和常数级空间复杂度下，对链表进行排序
排序算法中时间复杂度为 O(nlogn) 的是归并排序，堆排序，快速排序（最差时间复杂度是O(n2)）
其中最适合链表的排序算法是归并排序。

2、归并排序的实现方法

归并排序基于分治算法。通常使用自顶向下的递归实现方式，需要使用栈，空间复杂度为O(logn)
如果要达到 O(1) 的空间复杂度，则需要使用自底向上的实现方式。

二、自顶向下归并排序 – 递归版本实现

在这里插入图片描述
递归分割，拆分成单个节点：
1、找到链表的中间节点，拆分成左右两部分。并且将左右链表断开。
2、利用递归将断开之后的左右链表再次断开，只到只有一个或者0个节点的左右链表。

合并：
进行比较之后合并，参考21.合并两个有序链表

var sortList = function(head) {
    // 去检验最后的拆分的节点，保证只有0个或者1个
    if(!head || !head.next) return head;

    // 1、找到链表的中间节点，拆分成左右两部分。并且将左右链表断开
    let slow = head,fast = head;  // 使用快慢指针找到中间节点
    let preSlow = null; // 确定slow之前的节点，方便断链

    while(fast && fast.next){
        preSlow = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    // 断开左右链表,此时左链的头指针是head,右链的头指针是slow
    preSlow.next = null;
    
    // 2、将断开之后的左右链表再次断开，只到只有一个或者0个节点的左右链表。
    const l = sortList(head);
    const r = sortList(slow);
    // 3、最后得到的左边一个节点l, 和右边一个节点r,两者进行排序合并。
    return merge(l,r);
};

// 将链表进行合并，参考21题
var merge = function(l1,l2){
    // 虚拟头节点
    let dummyNode = new ListNode(-1);
    let pre = dummyNode;
    while(l1 && l2){
        if(l1.val < l2.val){
            pre.next = l1;
            l1 = l1.next;
        }else{
            pre.next = l2;
            l2 = l2.next;
        }
        pre = pre.next;
    }
    // 处理当某个链表为空的情况
    if(l1) pre.next = l1;
    if(l2) pre.next = l2;

    return dummyNode.next;
}