Sort a linked list in O(n log n) time using constant space complexity.

这道题目非常简短的一句话。给链表排序，看到nlogn。我们能够来简单复习一下排序。

首先说一下这个nlogn的时间复杂度（依据决策树我们能够得出这个界限）。是基于比較排序的最小上限，也就是说。对于没有一定范围情况的数据来说。最快的排序思路就是归并和高速排序了（当然详细的參数系数还是由更详细的设置决定的）。对于数组的话，假设使用归并排序，不是in place的，由于我们须要额外申请一个（N）空间用于merge的时候使用，所以导致了数据的复制和传递，因此不适合作为主存排序。（内存的数据变化量但是惊人的呀）。

但是，对于链表的归并排序，就能够做到in place，原因在于。链表本来就是一个动态的数据结构，我们在merge的时候改变一下指针的指向就OK了。之前，我在帮公司写一个项目的时候，support组提供的数据结构接口不是非常惬意，我就自己封装了一个利用归并来排序的链表，感觉用起来还行（强迫症？）。顺便提一下，最主要的排序。插入排序。n^2的时间复杂度；以及历史上第一次突破平方界限的排序。希尔排序，事实上就是插入排序的改良版。时间复杂度取决于因子的选取（详细我忘记了），废话太多了>.< orz。