已知两个长度分别为 m 和 n 的升序链表，若将它们合并为一个长度为 m+n 的降序链表，则最坏情况_

返回主页

[数据结构 P1493] 已知两个长度分别为 m 和 n 的升序链表，若将它们合并为一个长度为 m+n 的降序链表，则最坏情况

学习人数: 4.9k

正确率: ??%

答案解析

题目描述

未通过

已知两个长度分别为 m 和 n 的升序链表，若将它们合并为一个长度为 m+n 的降序链表，则最坏情况下的时间复杂度是（）

A. O(n)

B. O(m * n)

C. O(min(m, n))

D. O(max(m, n))

上面问题的答案是：

A 选项

B 选项

C 选项

D 选项

上一题

下一题

加入错题本

个人笔记

已有17条笔记

登录后提交答案

2 个回答 (点击展开回答)

哔哔哔

2023年10月27日 16:40

最少次数的比较：走完短的链表发现短链表的最小值还是比长链表最大值大；这种种情况下的比较次数是n次，复杂度为：O(min(m,n))；最大次数的比较：那当然是一步一比较，两链表的值是穿插着的就好比value值分别为：1 3 5 7和2 4 6 8 10的两个链表，可以多带入点值发现此种情况下的比较次数为n+m-1（一步一比较的情况下剩下的最后一个值不用比较直接链上就对了）；所以说时间复杂度为O(N+M-1)，最高次都是一次，选择的时候应该选择最大的那个数了,道理跟O(n+10000）为O(n)是一样的，所以答案是D为：O(MAX(M,N))

wzj123123

2022年11月23日 18:19

最小值的话，答案不该是C吗？