【链表】sort-list（归并排序）

比较好的博客：

https://juejin.im/post/59fbe7766fb9a0451c39bf21#1

对链表进行排序，考察的是排序算法，对几种常用的排序算法必须要非常熟悉。先来直观理解一下，然后再编程实现。

小涵涵是一个初级AI，有[2,3,1,4,6,5]这几个数，小涵涵想要把它进行从小到大的排序，她就想啊，怎么才能按照从小到大的顺序排列呢？想到一个idea,可以比较挨着的两个数，把大数往后面排，这样遍历n次之后，就是有序的啦。来分析一下复杂度：最坏情况是，每次比较都要进行交换，一共交换n(n-1)/2次，最好的情况是，本来就是有序的，在一次遍历之后，没有交换的数，那么就可以停止遍历了，复杂度就是O(n)。这就是最简单的冒泡排序。

还有什么办法呢？小涵涵想，还可以把最小的数放在第一个位置，第二小的数放在第二个位置…这样做的话，一共要比较n(n-1)/2，最好最坏的复杂度都是O(n方），这就是选择排序。

还有什么办法呢，小涵涵想，还可以把一个数，插入到一个有序序列里，最好的情况是，本来就是有序的，比如[1,2,3,4],已经排好序列[1,2]，插入3的时候，比较3和前面序列最后一个数，发现比最后一个数大，就直接插入到最后一个位置，总共比较n次，最好时间复杂度是O(n)，最坏的情况就是O(n方）啦。这就是插入排序。把插入排序优化一下，有个gap，就是希尔排序。希尔排序时间复杂度为O(n的1.3次方）

em……聪明小涵涵意识到，排序其实可以理解为一个递归的过程，因为就是比较数的大小，把小的往前面仍，大的往后面仍嘛，两个数是这样，三个数也是这个思想。选一个数作为中间数，小于中间数的放在中间数左边，大于中间数的放在中间数右边，进行递归，这就是快速排序！最好时间复杂度为O(nlogn)，最坏情况O(n方）

不选一个数作为基准，而是每次都把list分为左右两个部分，对左右两个部分进行递归，这就是归并排序！！最好最坏复杂度都是O(nlogn)。

And,对于选择排序来说，有一个明显的缺点就是，每次遍历过程，无记忆性，利用二叉树结构，构造一个大顶锥，每次把锥顶的元素拿出来，放到end，对除了end之外的锥进行最大锥化，这就是堆排序！！最好最坏复杂度都是O(nlogn)。

print('-------------------------------------分割线---------------------------------------------------‘）

下面解题啦，参考

http://bookshadow.com/weblog/2014/11/21/leetcode-sort-list/

题目要求了时间复杂度，O(nlogn)时间复杂度的有快排，堆排序，记忆归并排序，根据链表特点，选择归并排序（不太懂why)

首先，找链表中点，有一个非常tricky的方式，快慢指针法