面试算法：单链表的归并排序

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

归并排序：归并排序对于数组来说，空间复杂度为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;
    }
}