首页 > 试题广场 > 将两个长度为 len1 和 len2 的升序链表,合并为一个
[单选题]
将两个长度为 len1 和 len2 的升序链表,合并为一个长度为 len1+len2 的降序列表,采用 归并算法,在最坏情况下,比较操作的次数与( )最接近 .
  • len1+len2
  • len1*len2
  • min(len1,len2)
  • max(len1,len2)
推荐
A
归并排序采用分治策略(分治法将问题成一些小的问题然后递归求解,而的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之)。
  1. len2的最大序列和len1的最大序列相互比较,较大的一个放到新链表中(假设len2的元素)
  2. 然后对比len2序列剩余元素的最大值继续和len1的最大值做比较,将较大的放入新链表中
  3. 依次类推,最坏的情况就是len2中的每个元素都要和len1做比较,而且len1相互之间再做比较,即len1+len2
编辑于 2019-11-25 14:17:28 回复(0)
A
首先链表反转的时间复杂度是O(n)和 O(m),然后将两个链表连接,(最优情况)当两个链表一个先走完,另一个没有动的时候结果最优,最优的时间为min(len1,len2);(最坏情况)当两个链表交替进行的时候,连接两个链表的时间最长len1+len2。
发表于 2019-11-22 18:18:31 回复(0)
选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)
答案选A
发表于 2019-11-22 16:14:32 回复(0)