将长度为n的单链表连接在长度为m的单链表之后的算法的时间复杂度为（ ）。
A. O(1) B. O(n) C. O(m) D. O(m+n)
链接只需要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
用户登录可进行刷题及查看答案
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后提交答案