上周面试的时候被问了一道对单链表使用归并排序，我的解法是这样的：
以下是我的代码
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
 |
1
moro Oct 19, 2015
|
 |
2
gamingcat1234 Oct 19, 2015  1
我觉得可以使用非递归的 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." |
 |
3
iShao Oct 19, 2015 via Android
看说明很像插入排序，也不需要递归
|
|
4
iShao Oct 19, 2015 via Android
@gamingcat1234
我手机上打开 stackoverflow 变成蓝色了，以前的屎黄色啥时候改版了？ |
 |
5
canesten Oct 19, 2015
这是面的哪家？
|
 |
6
linux40 Oct 19, 2015
这个就是递归调用执行的过程啊。。。
|
 |
8
Aksura Oct 19, 2015
|
|
10
Aksura Oct 20, 2015
|
Select Language