首页 > 试题广场 >

将两个长度为 len1 和 len2 的升序链表，合并为一个

[单选题]

将两个长度为 len1 和 len2 的升序链表，合并为一个长度为 len1+len2 的降序列表，采用归并算法，在最坏情况下，比较操作的次数与（）最接近 .

推荐

白驹之过隙

选A。

归并排序采用分治策略（分治法将问题分成一些小的问题然后递归求解，而治的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

编辑于 2019-11-25 14:17:28 回复(0)

Jino.

选A。

首先链表反转的时间复杂度是O(n)和 O(m)，然后将两个链表连接，（最优情况）当两个链表一个先走完，另一个没有动的时候结果最优，最优的时间为min(len1,len2);（最坏情况）当两个链表交替进行的时候，连接两个链表的时间最长len1+len2。

发表于 2019-11-22 18:18:31 回复(0)

菜鸡上路（已消毒）

举这个例子可以吗

len1：{1，3，5}

len2：{2，4，6}

两组链表的所有数据都得比

发表于 2020-03-22 15:33:33 回复(0)

安苒_

最好的情况就是链表a上所有的值都比链表b上的值要小，此时的时间复杂度就是min(len1,len2)最坏的情况就是两个链表恰好可以穿插，例如（1，3，5），另外一个是（2，4，6），此时的时间复杂度就是len1+len2

发表于 2022-11-14 15:26:58 回复(0)

不拉不拉

len1相互为什么比较，不是已经有序吗

发表于 2022-11-01 04:52:10 回复(1)

子沐-

答案选A

发表于 2019-11-22 16:14:32 回复(1)

我就是个弟弟1

选A

要得到降序链表，得到升序链表后翻转就可以了。

比较操作是发生在两个链表的元素之间的，最坏的情况是链表中的每个元素都进行了比较。

循环执行次数最多的情况就是：终止条件为 p1为null 且p2.next为null 或 p1.next为null&&p2为null

编辑于 2019-11-22 17:13:53 回复(0)

提交观点

问题信息

链表

上传者：zsw3

难度：

7条回答 542收藏 5997浏览