### Sort List

Sort a linked list in O(n logn) time using constant space complexity.

Example 1:

Input: 4->2->1->3Output: 1->2->3->4

Example 2:

Input: -1->5->3->4->0Output: -1->0->3->4->5

### analyze

• 问题一: 如何确认链表的中点?
• 问题二: 链表如何 merge?

slow          quickdummy  ->  1  ->  null
slow  quickdummy  ->  4  ->  2  ->  1  ->  null

slow   quickdummy  ->  1  ->  2  ->  null

1. 在 leftList 中找到比 rNode 小且最接近 rNode 的值 lNode;
2. 将 rNode 插入 lNode 的后面;

lNode                         rNodedummy -> 1 -> 3 -> null         2 -> 4 -> null
lNode            rNodedummy -> 1 -> 2 -> 3 -> null    4 -> null
var sortList = function(head) {  const dummy = new ListNode(0)  dummy.next = head  let head0 = dummy.next
let slow = dummy, quick = dummy  while (quick.next) {    quick = quick.next    slow = slow.next    quick.next && (quick = quick.next)  }  // if the slow list is equal to the quick list, it means the current list only has one node.  if (slow === quick) return dummy.next  let rightList = slow.next  slow.next = null  let leftList = dummy  return merge(sortList(leftList.next), sortList(rightList))}
var merge = function(leftList, rightList) {  const dummy = new ListNode(0)  dummy.next = leftList  let lNode = dummy  let rNode = rightList
while (lNode && rNode) {    while (lNode.next && lNode.next.val < rNode.val) {      lNode = lNode.next    }    let rNext = rNode.next    rNode.next = lNode.next    lNode.next = rNode    rNode = rNext  }  return dummy.next}

147、143、234