排序链表（JS实现）

1 题目
在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
示例 1:
输入: 4->2->1->3
输出: 1->2->3->4
示例 2:
输入: -1->5->3->4->0
输出: -1->0->3->4->5

2 思路
快速排序的链表方式，注意获取中点时，链表被断开成等分的两半，返回的是各部分的首节点

3代码
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var sortList = function(head) {

if (!head || !head.next) return head;

return sort(head);

function sort(linkHead) {
if (!linkHead || !linkHead.next) return linkHead;
let [head1, head2] = getMid(linkHead);
head1 = sort(head1);
head2 = sort(head2);
return merge(head1, head2);
}

function merge(head1, head2) {
if (!head1 || !head2) return head1 || head2;

let linkHead = null;
let list = null;
while(head1 && head2) {
if (head1.val < head2.val) {
if (!linkHead) {
linkHead = list = head1;
} else {
list.next = head1;
list = list.next;
}
head1 = head1.next;
} else {
if (!linkHead) {
linkHead = list = head2;
} else {
list.next = head2;
list = list.next;
}
head2 = head2.next;
}
}

if (head1) {
list.next = head1;
}

if (head2) {
list.next = head2;
}

return linkHead;
}

function getMid(linkHead) {
if (!linkHead) return [null, null];
let p = q = linkHead;
let pre;
while(p && q) {
pre = p;
p = p.next;
q = q.next ? q.next.next : q.next;
}
let head1 = pre && pre.next;
if (pre) pre.next = null;
return [linkHead, head1];
}
};