Leetcode 148. 排序链表

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

经典的分治算法应用，通过归并进行排序，需要用到一个与原数组相同长度的数组

归（分割）思想如上图所示，代码实现通过快慢指针来寻找链表的中点来分割指针

var spilitList = function(head) {
    if (head === null) {
        return null;
    }
    if (head.next === null) {
        return head;
    }

    let fast = head, slow = head;
    while (fast.next !== null && fast.next.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    let mid = slow.next;
    slow.next = null; // 将链表分成两部分

    let left = spilitList(head); // 前半部分
    let right = spilitList(mid); // 后半部分

    return merge(left, right); // 合并排序后的两部分
}

 治（排序）设置左右指针指向分割之后的链表，设置一个指针来合并。

var merge=function(head1,head2){
    let newList=new ListNode(0)
    let dumy=newList,left=head1,right=head2
    while(left!==null&&right!==null){
        if(left.val>=right.val){
            dumy.next=right
            right=right.next
        }else{
            dumy.next=left
            left=left.next
        }
        dumy=dumy.next
    }
    //一边链表没走完
    if(left!=null){
        dumy.next=left
    }
    if(right!=null){
        dumy.next=right
    }
    return newList.next
}