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

admin2009-03-15  36

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

选项

答案O(n)

解析 对于一个具有n个结点的单链表,若指针已指向p,在其后插入元素,只需直接插入即可,时间复杂度为O(1);在给定x值的结点后插入元素,它将头结点开始查找,找到x后,再插入。
转载请注明原文地址:https://kaotiyun.com/show/5C1p777K
0

最新回复(0)