单链表添加节点的时间复杂度：指定操作是O(n)还是O(1)？

结论先行 #

该操作的最坏时间复杂度为固定常数级，属于O(1)，不属于O(n)。 #

具体推导过程 #

我们分两种常见的调用场景展开说明：

• 场景1：未提前缓存第10个节点的指针，只能从头节点开始遍历查找
  单链表的遍历规则是只能从头部节点依次向后访问，要找到第10个节点只需要固定遍历9次即可定位，后续插入节点的操作只需修改两个节点的next指针，耗时固定。
  注意：这里的遍历次数是固定常数10，和单链表的总长度n没有关联，不管单链表总长度是10还是10^8，整个插入操作的耗时都不会随n的增长而变大。
• 场景2：已提前持有第10个节点的引用
  这种情况下不需要执行遍历操作，直接修改两个节点的指针即可完成插入，耗时也是固定常数。

常见误区说明 #

很多人会误以为单链表的任意位置插入都是O(n)复杂度，这个结论的前提是「插入位置的序号k是和n强相关的变量」，比如要求在倒数第k个节点后插入、或者在第n/2个节点后插入，此时遍历次数会随n线性增长，才属于O(n)。而本题中插入位置固定在第10个节点之后，遍历次数是和n无关的常数，因此复杂度为O(1)。

内容的提问来源于stack exchange，提问作者ap0808