128

题目

分治算法+合并有序链表

var sortList = function(head) {
  return tosortList(head, null);
};
function tosortList(head, tail){
  if(head === null)return head;
  if(head.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;
    }
  }
  let mid = slow;
  return merge(tosortList(head, mid), tosortList(mid, tail));
}
function merge(l1,l2){
  if(!l1&&!l2)return null;
  if(!l1)return l2;
  if(!l2)return l1;
  if(l1.val<l2.val){
    l1.next = merge(l1.next,l2);
    return l1;
  }else{
    l2.next = merge(l1,l2.next);
    return l2;
  }
}