链表排序

链表适合插入和删除，不适合检索，尤其是单向链表中寻找节点的父节点。

快排：可参考快排常见的三种策略。除了插入策略之外，都不太适合链表，因为需要寻找父节点。
堆排序：堆排序似乎没有大的问题，但是空间复杂度N。
归并排序：归并排序对于数组来说，空间复杂度为N，被人诟病。但是在链表中，其空间复杂度为常数，nlogn的时间复杂度，以及稳定性。无疑是链表排序中最优选择。

对链表的归并排序和数组大同小异，不过有几个值得注意的点。

1. 使用快慢指针寻找中间节点，而不用遍历链表得到长度，再遍历寻找中间节点。
2. 对链表的sort和merge中不要使用索引了，全部可以使用节点。尽量不要在链表中使用索引，效率低。
3. 拆分链表的时候将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];
    }