O(1)时间才删除链表节点的问题

Question

书上说顺序查找链表非尾节点时间复杂度为O(1)，尾节点的为O(n)，所以平均时间复杂度为O(1)，为什么呢？为什么不是这样的呢？

Answer 1

删除这个动作本身是O(1)没错，但是你得遍历节点，才能找到要删除的节点，这个复杂度是O(n)，所以除非是清空链表或者删除头节点，否则不可能是O(1)。