题目描述：

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
示例 1:

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

示例 2:

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

算法实现:

  1. /**
  2.  * Definition for singly-linked list.
  3.  * function ListNode(val) {
  4.  *     this.val = val;
  5.  *     this.next = null;
  6.  * }
  7.  */
  8. /**
  9.  * @param {ListNode} head
  10.  * @return {ListNode}
  11.  */
  12. var sortList = function(head) {
  13.         if (head === null || head.next === null)
  14.             return head
  15.         let slow = head,
  16.             fast = head
  17.         while (slow.next && fast.next && fast.next.next) {
  18.             slow = slow.next
  19.             fast = fast.next.next
  20.         }
  21.         let mid = slow.next
  22.         slow.next = null
  23.         let right = mid
  24.         let left = head
  25.         return merge(sortList(left), sortList(right))
  26.     };
  27. let merge = function(left, right) {
  28.     let res = new ListNode(null)
  29.     let p1 = left,
  30.         p2 = right
  31.     let p = res
  32.     while (p1 && p2) {
  33.         if (p1.val < p2.val) {
  34.             let s = p1
  35.             p1 = p1.next
  36.             s.next = null
  37.             p.next = s
  38.             p = s
  39.         } else {
  40.             let s = p2
  41.             p2 = p2.next
  42.             s.next = null
  43.             p.next = s
  44.             p = s
  45.         }
  46.     }
  47.     if (p1)
  48.         p.next = p1
  49.     if (p2)
  50.         p.next = p2
  51.     return res.next
  52. }

思考：

看起来很简单实操却很难的一道题，由于控制了时间复杂度和空间复杂度，导致只能用归并排序的方法，以前并没有使用过这种方法，大致的思路是由底向上逐渐排序归并最后形成正确的链表。

总结：

很好的一道题，值得思考。