已知两个长度分别为m 和n 的递增单链表，若将它们合并为一个长度为m+n 的递减单链表，则最好情况下的时间复杂度是______。
A. O(n)
B. O(m)
C. O(m×n)
D. O(m+n)
这题答案是不是不对，最好是O(m)或O(n)，最坏才是O(m+n)吧？
在之前的题目做过一个类似的题目，只不过那个题目给的两个链表的条件是递增的，这两题的解法几乎是一样的：一般建立一个新的链表来存放它们的合并链表，分别比较两个链表的首结点，若是需要合并后递减，则将大的放入新链表；若是递减则将小的放入。
以下是本题计算思路：
1.最坏时间复杂度：
在每次比较都需要进行插入操作，且两个链表的结点交替插入新链表，此时就需要进行m+n次比较和插入操作。例如：
L1：5->3->1 （m=3）
L2：6->4->2 （n=3）
依次比较L1与L2的头节点后将大的那个插入新链表，直至一个链表所指为空即结束，得到以下插入序列（用{}表示每一次比较插入后的结果）：
{6},{6->5},{6->5->4},{6->5->4->3},{6->5->4->3->2},{6->5->4->3->2->1}
一共m+n即6次，故而时间复杂度可以写为O(m+n)。
2.最好时间复杂度：
当长度为m，n的两个链表在比较至一半时候，可能有一个链表已经为空了，那么直接将剩下那个链表的头节点直接链接在新链表的尾结点即可，例子1：
L1：2->1 (m=2)
L2：5->4->3 (n=3)
比较插入序列如下：
{5},{5->4},{5->4->3->2->1}
时间复杂度为O(n)。
例子2：
L1：5->4->3 (m=3)
L2：2->1 (n=2)
时间复杂度O(m)。
开始以为最好是O(min(n,m))，但是仔细一想后发现这样是不够严谨的，有可能有特殊情况，也就是一个序列的首结点表示的元素大小比另一个序列的最末一个都小，这个时候就不是O(min(m,n))了，有可能是m，n中大的那一个，也有可能是小的那一个。
（ps：以上观点若有误，欢迎指正，一起加油哦~）
快乐小土狗 回复 Djiangxu： 你举的例子不恰当，题目说的L1和L2是递增的，你给例子是递减的。
Djiangxu 回复 快乐小土狗： 感谢提醒，我把题目看成两个递减单链表了。
123
456 为例
从新空链表头部把更小的插入
1
21
321
4321
54321
654321
复杂度 O(m+n)
实际上和合并成 递增链表并无不同，只是插入数据的时候一个从尾部插入，一个从头部插入。
Djiangxu 回复 Austin00： 这应该是最坏的吧
Djiangxu 回复 Djiangxu： 不好意思，题目看错了
Austin00 回复 Austin00： 你那个是。递增 到 递增。递增到递减，剩下的还是要一个一个放进去的
先将其和并为一个递增的链表(最好的O(max(m,n)))，再翻转时间复杂度为O(m+n),故最好是O(m+n)
北方 回复 iheanu_： 一派胡言
LEK 回复 iheanu_： 在最好情况下，两个递增单链表的最小元素分别位于链表的头部。 合并这两个递增单链表为递减单链表，可以采用类似归并排序的思想：比较两个链表的当前节点的值，取较小的节点作为新链表的当前节点，并向后移动。 假设链表1的长度为m，链表2的长度为n。在最好情况下，两个链表中的元素是交替排列的，即链表1的元素都比链表2的元素小，或者链表2的元素都比链表1的元素小。这种情况下，只需要遍历两个链表一次即可完成合并。 所以，最好情况下的时间复杂度是O(m+n)。选项D正确。
huyufeu1009 回复 LEK： 一派胡言，你这样合并之后的链表是递增的。
huyufeu1009 回复 北方： 有啥问题？
D
用户登录可进行刷题及查看答案
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后提交答案