leetcode sortList

donnice 发表于 2014-7-31 15:57
诶，貌似只找到了C++的版本……

看看实现就行了 思想都是一样的

donnice 发表于 2014-7-31 01:38
你的解法和我的完全一样，惟一的区别就是你是复制了代码

nlogn的排序能有什么别的思路？ 而且思路一样， 用代码表达出来的不一样， bug-resistency也不一样。你写了不少可避免的代码， 这样的代码质量就算ac对于面试也不是好事， 更何况你也没ac。

我在qsort那留了个小破绽（不是bug）， 不知道你能看出来么╮(╯▽╰)╭

北美农民 发表于 2014-7-31 21:29
nlogn的排序能有什么别的思路？ 而且思路一样， 用代码表达出来的不一样， bug-resistency也不一样。你写 ...

你不会是想说append的return写错了吧。。。

donnice 发表于 2014-8-1 00:58
你不会是想说append的return写错了吧。。。

诶，难道不该是先把cur赋给新的node，然后再return node.next么

北美农民 发表于 2014-7-31 12:12
直接参考我的代码吧，  quick sort和merge sort都写了， 看注释。
你的代码太乱，不值得去花时间找bug。

那个，merge sort那部分有点没看懂啊，直接merge就能保证排好序了么？

北美农民 发表于 2014-7-31 12:12
直接参考我的代码吧，  quick sort和merge sort都写了， 看注释。
你的代码太乱，不值得去花时间找bug。

抱歉，看错了，但是这样写merge sort是用递归来实现的，不是常数空间吧，我一开始也是使用递归的方法写的，但是这样做空间复杂度是O(LOGN)至少

pyemma 发表于 2014-8-2 06:58
抱歉，看错了，但是这样写merge sort是用递归来实现的，不是常数空间吧，我一开始也是使用递归的方法写的 ...

题目没要求常数空间啊。

pyemma 发表于 2014-8-2 06:58
抱歉，看错了，但是这样写merge sort是用递归来实现的，不是常数空间吧，我一开始也是使用递归的方法写的 ...

对了， 求一段 nlogn排序 + 常数空间的实现？  谢谢。

北美农民 发表于 2014-8-2 08:16
对了， 求一段 nlogn排序 + 常数空间的实现？  谢谢。

自底向上地 merge sort，可以 O(1) space，O(nlogn) time
不过实现很 tricky，感觉不必深究。
有兴趣可以看这里：
http://lifexplorer.me/leetcode-sort-list/

Kimurate 发表于 2014-8-2 11:42
自底向上地 merge sort，可以 O(1) space，O(nlogn) time
不过实现很 tricky，感觉不必深究。
有兴趣可 ...

bottom up不tricky， 只是要一份implementation看看写的怎么样， 感觉很乱。

我记得在哪里看过真正应用中，O(logn)的栈空间复杂度是可以视为常数的效果。因为堆栈深度上限太有限了