题解 | #12.单链表的排序#

归并排序，1年前我都是用冒泡的，每次写都要debug好久好久，看了题解，用归并

注意：

1.将slow.next = null，很关键的一步

2.注意排序的是slow.next和head而不是slow和head

3.引入没用的结点充当头，最后返回empty.next

4.最后不要忘了合并剩余的leftorright

function sortInList(head) {
  if(head==null || head.next==null)  return head;  //0个元素或者1个元素
  
  let slow = head,
      fast = head.next;
  
  //快慢指针寻找链表中点->slow
  while(fast!=null && fast.next!=null){
    fast = fast.next.next;
    slow = slow.next;
  }
  let temp = slow.next;//中间右边的节点
  slow.next = null;
  
  //递归左右两边进行排序
  let left  = sortInList(head);
  let right = sortInList(temp);
  
  let empty = {};
  let pre = empty;
  
  //合并left和right两个链表
  while(left!=null && right!=null){
    if(left.val < right.val){
      pre.next = left;
      left = left.next;
    }else{
      pre.next = right;
      right = right.next;
    }
    pre = pre.next;
  }
  
  pre.next = left!=null ? left : right;//添加两块剩余的
  return empty.next;
}
module.exports = {
  sortInList: sortInList,
};