关于单链表插入算法时间复杂度的疑惑
发布网友
发布时间：2022-04-22 00:59
共2个回答
热心网友
时间：2024-02-06 22:32
应该是书上没有写清楚。如果第i个节点的指针已知，那么按照（2）的方法时间复杂度是O(1)。否则也要找第i个节点，复杂度也是O(n)。
热心网友
时间：2024-02-06 22:32
呵呵，
如果是要查找的话，那当然是o(n)了
但在实际使用时，我们一般是已知一个结点，例如结点p,要在它的后面插入一个结点q，
这时就是常数阶的复杂度了
q->next
=
p->next;
p->next
=
q;
