A-A+

对于一个具有n个结点的单链表已知p所指结点后插入一个新结点的时间复杂度是O(1)；在给定值

2022-08-12 20:14:50 问答库阅读 197 次

问题详情

对于一个具有n个结点的单链表，已知p所指结点后插入一个新结点的时间复杂度是O(1)；在给定值为x的结点后插入一个新结点的时间复杂度是【】。

请帮忙给出正确答案和分析，谢谢！

正确答案：O(n)
对于一个具有n个结点的单链表，若指针已指向p，在其后插入元素，只需直接插入即可，时间复杂度为O(1)；在给定x值的结点后插入元素，它将头结点开始查找，找到x后，再插入。