题解 | 单链表的排序

/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 the head node
 * @return ListNode类
 */
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,
};

用归并算法，首先要先分治，每次都寻找中间节点，用快慢指针。

然后弄成两个链表再合并

一定要设置退出归并的条件，就比如head==null && head.next=null;