面试题：双向链表排序

Question

今天面试被问到的一个问题，对于一个双向链表要对它排序。限制如下：时间复杂度平均要是O(nlgn),要避免最坏的O(n^2)的情况。空间复杂度是O(1)。这应该需要通过堆排序的改进来实现，想问一下大家有没有解法？

Answer 1

用堆排在查找子树的时候不是会十分蛋疼么。。。

我觉得还是快排吧，毕竟每次推进都是相邻节点。避免最坏情况就要处理好选取中轴的过程。

Answer 2

把链表和数组抽象化，swap函数调整双方的位置，然后用通用的排序方法进行排序。