难度：中等

    题目描述：
    在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

    示例：

    1. 输入: -1->5->3->4->0
    2. 输出: -1->0->3->4->5

    解题思路：
    image.png

    • 1、把长度为n的输入序列分成两个长度为n/2的子序列
    • 2、对这两个子序列分别采用归并排序
    • 3、将两个排序好的子序列合并成一个最终的排序序列
      1. var sortList = function(head) {
      2.   function mergeSort(node){
      3.       if(!node||!node.next){
      4.            return node;
      5.       }
      6.       let slowNode=node;
      7.       let fastNode=node;
      8.       //  找到中点
      9.       while(fastNode.next&&fastNode.next.next){
      10.           slowNode=slowNode.next;
      11.           fastNode=fastNode.next.next
      12.       }
      13.       let curNode=slowNode.next;
      14.       slowNode.next=null
      15.       let left = mergeSort(node)
      16.       let right = mergeSort(curNode)
      17.       return merge(left,right)
      18.   }
      19.   function merge(left,right){
      20.       let startNode = new ListNode(0)
      21.       let pre=startNode
      22.       let leftNode=left;
      23.       let rightNode=right
      24.       while(leftNode&&rightNode){
      25.           if(leftNode.val<=rightNode.val){
      26.               pre.next=leftNode
      27.               leftNode=leftNode.next
      28.           }else{
      29.               pre.next=rightNode;
      30.               rightNode=rightNode.next
      31.           }
      32.           pre=pre.next
      33.       }
      34.       if(leftNode){
      35.           pre.next=leftNode
      36.       }
      37.       if(rightNode){
      38.           pre.next=rightNode
      39.       }
      40.       return startNode.next
      41.   }
      42.   return mergeSort(head)
      43. };