我要招人

去企业版

首页 > 试题广场 >

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

[单选题]

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

```
len1+len2
```
```
len1*len2
```
```
min(len1,len2)
```
```
max(len1,len2)
```

查看答案及解析

推荐

白驹之过隙

选A。

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

len2的最大序列和len1的最大序列相互比较，较大的一个放到新链表中（假设len2的元素）
然后对比len2序列剩余元素的最大值继续和len1的最大值做比较，将较大的放入新链表中
依次类推，最坏的情况就是len2中的每个元素都要和len1做比较，而且len1相互之间再做比较，即len1+len2

编辑于 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)

yabo083

拿着个例子 a：1-3-5 b：2-4-6 先逆序，没有比较操作，所以跳过。 a：5-3-1 b：6-4-2 比较过程可能是这样： 6＞5，6定； 5＞4，5定； 4＞3，4定； 3＞2，3定； 2＞1，2定， 1没人比了，自然就定了。所以总次数是五次，接近A，网上解析：解析：对于归并算法而言包括两种情况：①两个链表还有剩下的元素时，则取两个链表中的最大值放入新链表中：②一个链无剩余元素，另一个链表有剩余元素时，直接将另一个链表直接放入新链表中。最多比较次数，m+n-1 最少比较次数，min(m,n) （注意时间复杂度和具体的执行次数完全是两码事）最坏时间复杂度O（max（m，n）) 最好时间复杂度O（min（m，n））

发表于 2024-05-21 20:13:26 回复(0)

我就是个弟弟1

选A

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

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

也可以根据链表归并算法的代码来看：https://www.nowcoder.com/profile/1329387/codeBookDetail?submissionId=54485941

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

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

提交观点

问题信息

链表

上传者：zsw3

难度：

8条回答 552收藏 6031浏览

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

问题信息

热门推荐

相关试题