### Sort List

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

Example 1:

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

Example 2:

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

### analyze

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

``````          slow
quick
dummy  ->  1  ->  null

slow  quick
dummy  ->  4  ->  2  ->  1  ->  null

slow  quick
dummy  ->  1  ->  2  ->  null``````

``````          slow   quick
dummy  ->  1  ->  2  ->  null``````

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

``````lNode                         rNode
dummy -> 1 -> 3 -> null         2 -> 4 -> null

lNode            rNode
dummy -> 1 -> 2 -> 3 -> null    4 -> null``````
``````var sortList = function(head) {
const dummy = new ListNode(0)

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