Sort List

    既然确定使用归并排序，我们就来思考归并排序实现的几个要素。

    1. 按长度等分链表，归并虽然不严格要求等分，但是等分能保证线性对数的时间复杂度。由于链表不能随机访问，故可以先对链表进行遍历求得其长度。
    2. 合并链表，细节已在 Merge Two Sorted Lists | Data Structure and Algorithm 中详述。

    在按长度等分链表时进行「后序归并」——先求得左半部分链表的表头，再求得右半部分链表的表头，最后进行归并操作。

    1. 在递归处理链表长度时，分析方法和 一致，count表示遍历到链表中间时表头指针需要移动的节点数。在纸上分析几个简单例子后即可确定，由于这个题需要的是「左右」而不是二叉搜索树那道题需要三分——「左中右」，故将count初始化为1更为方便，左半部分链表长度为length / 2, 这两个值的确定最好是先用纸笔分析再视情况取初值，不可死记硬背。
    2. 找到中间节点后首先将其作为右半部分链表处理，然后将其next值置为, 否则归并子程序无法正确求解。这里需要注意的是midNode是左半部分的最后一个节点，midNode->next才是链表右半部分的起始节点。
    3. 递归模型中左、右、合并三者的顺序可以根据分治思想确定，即先找出左右链表，最后进行归并(因为归并排序的前提是两个子链表各自有序)。

    复杂度分析

    遍历求得链表长度，时间复杂度为 O(n), 「折半取中」过程中总共有 \log(n) 层，每层找中点需遍历 n/2 个节点，故总的时间复杂度为 n/2 \cdot O(\log n) (折半取中), 每一层归并排序的时间复杂度介于 O(n/2) 和 O(n)之间，故总的时间复杂度为 O(n \log n), 空间复杂度为常数级别，满足题意。

    除了遍历链表求得总长外，还可使用看起来较为巧妙的技巧如「快慢指针」，快指针每次走两步，慢指针每次走一步，最后慢指针所指的节点即为中间节点。使用这种特技的关键之处在于如何正确确定快慢指针的起始位置。

    Java

    1. 异常处理不仅考虑了head, 还考虑了head->next, 可减少辅助程序中的异常处理。
    2. 使用快慢指针求中间节点时，将初始化为head->next可有效避免无法分割两个节点如1->2->null[^fast_slow_pointer]。
      • 求中点的子程序也可不做异常处理，但前提是主程序sortList中对head->next做了检测。
    3. 最后进行归并排序。

    复杂度分析

    同上。

    归并排序，总的时间复杂度是（nlogn),但是递归的空间复杂度并不是常数（和递归的层数有着关；递归的过程是自顶向下，好理解；这里提供自底向上的非递归方法；

    复杂度分析