两个未排序的单链表到一个排序的单链列表

Question

给定大小为M和N的两个未排序的单链表。任务是创建一个单独排序的链表。不应创建任何新节点。我想了两种方法。

方法1：

在MlogM和NlogN中分别对每个列表进行排序。然后合并两个已排序的列表
时间复杂度：O（MlogM+NlogN）

方法2：

将第二个列表附加到第一个列表的末尾。然后对列表进行排序
时间复杂度：O（（M+N）log（M+N））

哪种方法更好
还有更好的方法吗？

Answer 1

渐进地说，这是一样的。

如果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是合并排序

Answer 2

在任何情况下，近似1都是好的。如果

• n=2和m=3 nlogn=0.60，mlogm=1.43，nlogn+mlogm=2.03，而（n+m）log（n+m）=3.49

• n=2和m=30 nlogn=0.60，mlogm=44.31，nlogn+mlogm=44.91，而（n+m）log（n+m）=48.16

• n=2和m=300 nlogn=0.60，mlogm=743.14，nlogn+mlogm=743.74
  而（n+m）log（n+m）=748.96

• n=2和m=3000 nlogn=0.60，mlogm=10431.36，nlogn+mlogm=
  10431.96，而（n+m）log（n+m）=10439.18

• n=2且m=30000 nlogn=0.60，mlogm=134313.64，nlogn+mlogm=
  134314.24，而（n+m）log（n+m）=134323.46

• n=2和m=300000 nlogn=0.60，mlogm=1643136.38，nlogn+mlogm=1643136.98，而（n+m）log（n+m）=1643148.19

因为，这背后的明显原因是：无论如何，

(n+m) > n & (n+m) > m
log (n+m) >= log n
log (n+m) >= log m

而在n=m的情况下，

nlogn + mlogm = 2m logm
              = log m (power of 2m)
(n+m) log(n+m) = 2m log (2m)
               = log 2m (power of 2m)
and m(power of 2m) < 2m(power of 2m)

选择第一种方法的唯一简单原因是，与大型数组相比，对小数组数据进行排序的时间更少。