Sort-list

在O(n log n)的时间内使用常数级空间复杂度对链表进行排序

关键词： 链表 ; O(1）空间复杂度; O(nlogn)

我个人一开始的想法是 基数排序 并且在网上查了相关资料 发现大部分都说基数排序的空间复杂度不是O(1)
这一点我感觉到很纳闷！ 基数排序不是只要一个10容量的指针数组即可了嘛?（不深入）

但是我排除这基数排序的想法 是因为：
1.待排序列有正有负 (我觉得基数排序对正负数的区分不太好)
2.待排序的数字位数不固定(这个是最zhiming的）

后来看了一些题解 才看到大部分人都用的是递归的归并排序 （我也很纳闷为什么他们能通过）
但是有一个问题 归并排序的空间复杂度不是O(1) 而且题解中由大部分人用的还是递归 ，而我们知道递归是占用递归空间栈的空间的 O(logn) 所以说无论是递归形式的归并 还是非递归形式(用了栈的) 都是不可行的！

这里的想法借鉴了一部分 归并排序的递归和非递归实现（C代码）

虽然博客中还是用了tmp数组，但我zhishi借用了他归并的思想(两个两个归并，四个四个归并......)
不得不说 递归形式的归并排序 和非递归形式的归并 排序过程是完全不同的

后面就是要注意链表指针的移动了，这里面比较复杂，我也不知道该怎么说hh

最后一个段错误的可能就是当初始链表为空时， 有可能会发生段错误 所以在函数中记得另外判断一下
当head==NULL时 直接输出NULL;
千万注意链表的yuejie问题！！！！

总结：链表还是学的不够扎实，特别是指针移动，shasha搞不清。这道题思想虽然一开始就清楚了，但是写了好久才实现。