问个关于排序的面试题

[zeal7s]

上周面试的时候被问了一道对单链表使用归并排序，我的解法是这样的：

1. 通过快慢指针将链表一分为二
2. 递归调用排序算法分别对两个链表进行排序
3. 将两个排好序的链表合二为一

以下是我的代码
https://gist.github.com/fxxz/058689f7ecfb4633755b

结果面试官不满意我的解法，他说没必要遍历链表的一半来取得链表中点，这样效率不是最高的。如果我没记错的话，他的做法大概描述如下：

排序第一个 Node ，发现已排序，就归并前两个 Node 。已排好前两个 Node ，接着递归排第 3 和第 4 个 Node 。然后递归排第 1 ， 2 ， 3 ， 4 个 Node 。这时候应该递归地把第 1 ， 2 ， 3 ， 4 个 Node 和第 5 ， 6 ， 7 ， 8 个 Node 归并，但是 5 ， 6 ， 7 ， 8 还没排好，应该一层层递归下去把 5 ， 6 ， 7 ， 8 个 Node 排列好。以此类推，直到链表末尾。

听完面试官的做法，楼主有一种豁然开朗的赶脚，但是水平有限，实在写不出这样的归并排序。求问各位 V 友代码应该肿么写？ THX

[moro]

他的意思是插入排序。
看这里 https://zh.wikipedia.org/wiki/%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F

[gamingcat1234]

我觉得可以使用非递归的 merge sort ？
可以参考 http://stackoverflow.com/questions/7685/merge-sort-a-linked-list 里面 ShitalShah 的回答。
他说了下面这些，好像很符合你的要求。
"Lot of other code on Internet and StackOverflow is horribly bad. There are people trying to get middle point of the list, doing recursion, having multiple loops for left over nodes, maintaining counts of ton of things - ALL of which is unnecessary."

[iShao]

看说明很像插入排序，也不需要递归

[iShao]

@gamingcat1234
我手机上打开 stackoverflow 变成蓝色了，以前的屎黄色啥时候改版了？

[canesten]

这是面的哪家？

[linux40]

这个就是递归调用执行的过程啊。。。

[linux40]

@linux40 这才不是什么插入

[Aksura]

@linux40 看描述确实是归并排序自顶向下递归的执行路径，但是看 @gamingcat1234 提到的那个帖子里的回答，也比较像，难道是题主 @zeal7s 听面试官说的时候理解有偏差？

[linux40]

@Aksura 那个贴子的最高票也是找中间指针，别的没看了。。。

[Aksura]

@linux40 那个帖子里的 “ ShitalShah ” 的回答(不是最高票的)中的代码是可行的，执行顺序类似题主 @zeal7s 的描述，但是不是用递归。

[linux40]

@Aksura 本来就可以不用递归啊，先一个一个为一对地排，再两个两个为一对地排，再四个四个为一对地排。。。

[zeal7s]

@linux40 赶脚用递归是为了使代码更容易理解。。。

[linux40]

@zeal7s 写着方便也是一个原因。。。。