算法：98.链表排序

https://www.lintcode.com/problem/sort-list/description

描述

在 O(nlogn) 时间复杂度和常数级的空间复杂度下给链表排序。

样例

给出，给它排序变成.

挑战

分别用归并排序和快速排序做一遍。

思路

简单的插入排序，先将节点从链表中分离出来，然后从头开始比较，找到合适的位置再插入。O(n^2)的时间复杂度。

上面的实现简单，但效率较低，是O(n^2)的时间复杂度。

合并排序：

合并排序还是容易实现非递归的，步长从1逐渐增长到1/2，完成合并。外层循环为logn，循环内部需要实现一个logn的链表截取，logn的链表合并。整体是logN*logN，算是实现了挑战。

快速排序递归版本：

快速排序的非递归实现没有想到好的实现，使用了递归，所需的额外空间就不是常数级了。