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

admin2015-12-30 17

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

选项 A、O(n)
B、O(m×n)
C、O(min(m，n))
D、O(max(m，n))

答案D

解析两个升序链表合并，两两比较表中元素，每比较一次确定一个元素的链接位置(取较小元素，头插法)。当一个链表比较结束后，将另一个链表的剩余元素插入即可。最坏的情况是两个链表中的元素依次进行比较，直到两个链表都到表尾，即每个元素都经过比较，时间复杂度为O(m+n)=0(max(m，n))。

转载请注明原文地址:https://kaotiyun.com/show/L7xi777K

计算机408

相关试题推荐

随机试题

最新回复(0)