将长度为n的单链表连接在长度为m的单链表之后的算法的时间复杂度为( )。
A. O(1) B. O(n) C. O(m) D. O(m+n)
N诺智能批改可自动批改答案并给出反馈,每次使用将消耗 1个诺币
您当前的诺币数量: 个
N诺正在智能批改,预计需要30秒,请稍候...
链接只需要o(1)的复杂度,但是准备的复杂度为o(m)
答案错误,正确选c
需要先到 m 链表最后
链接,需要找到被链接链表的尾巴,才能链接上,链接操作复杂度是o(1),但是准备工作的时间复杂度是o(m)
首先:遍历长度m的单链表以找到它的最后一个节点; 其次:将长度为n的单链表的第一个节点插入到m的末尾
1.找M链的尾结点 O(m) 2.尾结点next指针指向N链表的头节点
不是求两个链表链接后的时间复杂度,而是把n接在m后这一过程需要的时间复杂度。
即只需要遍历m的长度即可
遍历长度为m的链表找到尾结点,然后在指向长度为n的链表的头就行
要找到长度为m的单链表的最后一个元素
Starhreat 回复 wxw: 总单链表的长度为M+N,找到最后一个元素是时间复杂度不是O(n+m)
C
登录后提交答案