链表适合插入和删除，不适合检索，尤其是单向链表中寻找节点的父节点。
快排：可参考快排常见的三种策略。除了插入策略之外，都不太适合链表，因为需要寻找父节点。
堆排序：堆排序似乎没有大的问题，但是空间复杂度N。
归并排序：归并排序对于数组来说，空间复杂度为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;
}
}
下面代码是对数组的归并排序，可以对照比较一下：
public static void sort(int arr[], int left, int right) {
if (left < right) {
int mid = (left + right) / 2; // 中间索引
sort(arr, left, mid);
sort(arr, mid + 1, right);
merge(arr, mid, left, right);
}
}
public static void merge(int[] arr, int mid, int left, int right) {
int[] temp = new int[right - left + 1]; // 被人诟病的空间复杂度
int i = left, j = mid + 1, k = 0; // merge
while (i <= mid && j <= right) {
if (arr[i] < arr[j]) temp[k++] = arr[i++];
else temp[k++] = arr[j++];
}
while (i <= mid) temp[k++] = arr[i++];
while (j <= right) temp[k++] = arr[j++];
// 将临时数组的内容复制回去
for (i = 0; i < temp.length; i++) arr[left + i] = temp[i];
}
