在n个节点的循环单列表中，在某个指针指向的节点之前插入一个节点的时间复杂度

Question

我认为它是O(N(，因为在循环单列表中，指针访问N个节点，因此要插入的节点位于当前节点之前。

我说对了吗？

Answer 1

通常的遍历和插入需要O(N)时间。但是，如果可以修改节点，也可以在O(1)中完成
让列表看起来像A -> B-> C -> D -> A，我们得到了一个指向C的指针，我们必须插入E。现在，创建一个C的副本，并将其插入C本身之后。该列表现在看起来像A -> B-> C -> C(copy) -> D -> A。现在，我们可以修改原始C节点的值来存储E节点的值，因此列表现在变成A -> B-> E -> C -> D -> A。由于您只创建了一个节点并将其插入到位，因此它需要O(1)的时间复杂性。