这是一个创建于 3358 天前的主题，其中的信息可能已经有所发展或是发生改变。
上周面试的时候被问了一道对单链表使用归并排序，我的解法是这样的：
- 通过快慢指针将链表一分为二
- 递归调用排序算法分别对两个链表进行排序
- 将两个排好序的链表合二为一
以下是我的代码
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 2015-10-19 13:42:24 +08:00
|
 |
2
gamingcat1234 2015-10-19 13:57:39 +08:00  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 2015-10-19 14:02:57 +08:00 via Android
看说明很像插入排序，也不需要递归
|
|
4
iShao 2015-10-19 14:09:09 +08:00 via Android
@gamingcat1234
我手机上打开 stackoverflow 变成蓝色了，以前的屎黄色啥时候改版了？ |
 |
5
canesten 2015-10-19 16:20:40 +08:00
这是面的哪家？
|
 |
6
linux40 2015-10-19 19:58:17 +08:00
这个就是递归调用执行的过程啊。。。
|
 |
8
Aksura 2015-10-19 20:03:06 +08:00
|
|
10
Aksura 2015-10-20 11:18:46 +08:00
|
Select Language