Sort List
Sort a linked list in O(n log n) time using constant space complexity
在nlogn的复杂度下对一个链表进行排序。
思路:在底层数据实现的条件下能达到nlogn复杂度的排序方法有以下几种,
快排,在单链表条件下实现,有一个high--的倒退动作无法完成(或者说这个动作的完成本身就需要O(n)的复杂度)
归并排序,在链表情况下,取中间值的操作复杂度大于O(1),平均复杂度应该是O(logn)。
希尔排序,链表情况下,无法进行跨步式前进,->next仍然需要读一次内存,所以实现出来的效率甚至会高于O(n2)。
堆排序,如果把链结构改成树结构,建堆的时间是nlogn,但是题中的节点并不具备两个引用域分别保存左子树和右子树。如果另行申请空间,空间复杂度为O(n),不符合常量空间的要求。
接下来考虑快排,归并和希尔排序中各个操作的频率,首先可以排除掉希尔排序,快排中high--操作一共有的次数。