首页
题库
面试
求职
学习
竞赛
More+
所有博客
搜索面经/职位/试题/公司
搜索
我要招人
去企业版
登录 / 注册
首页
>
试题广场
>
将两个长度为 len1 和 len2 的升序链表,合并为一个
[单选题]
将两个长度为 len1 和 len2 的升序链表,合并为一个长度为 len1+len2 的降序列表,采用 归并算法,在最坏情况下,比较操作的次数与( )最接近 .
len1+len2
len1*len2
min(len1,len2)
max(len1,len2)
查看答案及解析
添加笔记
邀请回答
收藏(542)
分享
7个回答
添加回答
8
推荐
白驹之过隙
选
A
。
归并排序
采用
分治
策略(分治法
将问题
分
成一些小的问题然后递归求解,而
治
的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之
)。
len2的最大序列和len1的最大序列相互比较,较大的一个放到新链表中(假设len2的元素)
然后对比len2序列剩余元素的最大值继续和len1的最大值做比较,将较大的放入新链表中
依次类推,最坏的情况就是len2中的每个元素都要和len1做比较,而且len1相互之间再做比较,即len1+len2
编辑于 2019-11-25 14:17:28
回复(0)
24
Jino.
选
A
。
首先链表反转的时间复杂度是O(n)和 O(m),然后将两个链表连接,
(最优情况)当两个链表一个先走完,另一个没有动的时候结果最优,最优的时间为
min(len1,len2)
;(最坏情况)当两个链表交替进行的时候,连接两个链表的时间最长len1+len2。
发表于 2019-11-22 18:18:31
回复(0)
13
菜鸡上路(已消毒)
举这个例子可以吗
len1:{1,3,5}
len2:{2,4,6}
两组链表的所有数据都得比
发表于 2020-03-22 15:33:33
回复(0)
2
安苒_
最好的情况就是链表a上所有的值都比链表b上的值要小,此时的时间复杂度就是min(len1,len2)最坏的情况就是两个链表恰好可以穿插,例如(1,3,5),另外一个是(2,4,6),此时的时间复杂度就是len1+len2
发表于 2022-11-14 15:26:58
回复(0)
2
不拉不拉
len1相互为什么比较,不是已经有序吗
发表于 2022-11-01 04:52:10
回复(1)
1
子沐-
答案选A
发表于 2019-11-22 16:14:32
回复(1)
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
难度:
7条回答
542收藏
5998浏览
热门推荐
相关试题
假定一个待哈希存储的线性表为(32...
哈希
评论
(1)
5.下列判断正确的是( )
资料分析
言语理解与表达
资料分析
评论
(1)
《拳皇97》最后BOSS是谁?
游戏常识
评论
(1)
《魔兽世界》中,下列不属于玩家可以...
游戏常识
评论
(1)
你有没有崇拜的偶像,你欣赏他/她身...
通用能力
评论
(1)
扫描二维码,关注牛客网
意见反馈
下载牛客APP,随时随地刷题