链表适合插入和删除，不适合检索，尤其是单向链表中寻找节点的父节点。
归并排序：归并排序对于数组来说，空间复杂度为N，被人诟病。但是在链表中，其空间复杂度为常数，nlogn的时间复杂度，以及稳定性。无疑是链表排序中最优选择。
对链表的归并排序和数组大同小异，不过有几个值得注意的点。
使用快慢指针寻找中间节点，而不用遍历链表得到长度，再遍历寻找中间节点。
对链表的sort和merge中不要使用索引了，全部可以使用节点。尽量不要在链表中使用索引，效率低。
拆分链表的时候将mid.next置为null，不然可能出现循环链表或程序错误。
链表归并排序参考代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode sortList(ListNode head) {
if(head == null || head.next == null) return head;
ListNode mid = getMidNode(head);// 获取中间节点
ListNode left = head;
ListNode right = mid.next;
mid.next = null; // 这一点很重要，不然可能出现循环链表
return merge(sortList(left),sortList(right));
}
// 合并链表，代码比较长，但是很好理解，头节点需要单独考虑一下
public ListNode merge(ListNode left, ListNode right){
if(left == null) return right;
if(right == null) return left;
ListNode head = null, p = null; // head 头节点，p用于遍历操作
while(left != null && right != null){
if(head == null){
if(left.val < right.val){
head = left;
left = left.next;
}else{
head = right;
right = right.next;
}
p = head
}else{
if(left.val < right.val){
p.next = left;
left = left.next;
}else{
p.next = right;
right = right.next;
}
p = p.next;
}
}
// 对剩下的节点进行merge
if(left != null) p.next = left;
else p.next = right;
return head;
}
// 使用快慢指针快速找到中间节点
public ListNode getMidNode(ListNode node){
if(node == null || node.next == null) return node;
ListNode low = node;
ListNode fast = node;
while(fast.next != null && fast.next.next != null){
low = low.next;
fast = fast.next.next;
}
return low;
}
}
