给定两个大小为 M 和 N 的未排序单链表。任务是创建一个排序的链表。不应创建新节点。
我想到了两种方法。
方法一:
分别对 MlogM 和 NlogN 中的每个列表进行排序。然后合并两个排序列表。
时间复杂度:O( MlogM + NlogN )
方法 2:
将第二个列表附加到第一个列表的末尾。然后对列表进行排序。
时间复杂度:O( (M + N) log(M + N) )
哪种方法更好？
还有更好的方法吗？
最佳答案
渐近地讲 - 它是一样的。
如果n<m然后:
O(nlogn+ mlogm) = O(mlogm)
and
O(n+m)log(n+m)) = O(nlog(n+m) + mlog(n+m)) = O(nlog(m) + mlog(m)) = O(mlogm)
对称地，如果m<n都是O(nlogn)
其实对于n=m , 方法 1 是 merge sort 的第一步
关于performance - 两个未排序的单链表到一个已排序的单链表，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12286510/