链表排序

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

输入：head = [4,2,1,3] 输出：[1,2,3,4]

因为链表不支持随机访问，所以用归并排序将其拆分成小段链表，排序后再连接起来效率最高。
该题是三个小题的组合：归并排序 + 双指针找单链表中点 + 合并两个排序链表。

可参考https://chun53.top/967.html和归并排序文章

对链表自顶向下归并排序的过程如下。

1. 找到链表的中点，以中点为分界，将链表拆分成两个子链表。寻找链表的中点可以使用快慢指针的做法，快指针每次移动 2 步，慢指针每次移动 1步，当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中点。
2. 对两个子链表分别递归成单个结点。再合并成有序子链表。
3. 将两个排序后的子链表合并，得到完整的排序后的链表。

上述过程可以通过递归实现。递归的终止条件是链表的节点个数小于或等于 1，即当链表为空或者链表只包含 1个节点时，不需要对链表进行拆分和排序。

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/7WHec2/solution/lian-biao-pai-xu-by-leetcode-solution-0rjx/
来源：力扣（LeetCode）

时间复杂度：$O(n\log n)$，其中 n 是链表的长度

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var sortList = function(head) {
    return finmidsort(head,null)
};
function ListNode(x){
    this.val = x;
    this.next = null;
}
function Merge(pHead1, pHead2)//链表合并
{
    // write code here
    if (!pHead1) return pHead2;
    if (!pHead2) return pHead1;
    let cur=new ListNode(0);
    let head=cur;
    while(pHead1 && pHead2){
        if (pHead1.val <=pHead2.val){
            cur.next = pHead1;
            pHead1=pHead1.next;
        }
        else {
            cur.next = pHead2;
            pHead2=pHead2.next;
        }
        cur=cur.next;
    }
    if (pHead1) cur.next = pHead1;
    else cur.next = pHead2;
    
    return head.next;
    
}
function finmidsort(head,tail){
    if (head === null) {//判断为null或只有一个节点
        return head;
    }
    if (head.next === tail) {//如果节点的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;//mid为新链表的头结点，故将tail设置为mid来分割2个链表
    let left = finmidsort(head,mid);//递归到单个节点
    let right = finmidsort(mid,tail);
    return Merge(left, right);//再归并
}