含n个节点的循环单链表中，在指定指针所指节点前插入节点的时间复杂度是多少？

核心提问梳理 #

• 基础问题：包含n个节点的循环单链表中，在某指针指向的节点之前插入新节点的时间复杂度是多少？
• 提问者原有判断：该操作时间复杂度为O(N)，理由是循环单链表无反向指针，必须顺着指针遍历完全部n个节点，才能定位到目标节点的前驱位置完成插入。

判断结论 #

• 提问者的判断在纯单向循环单链表的常规操作逻辑下是正确的，但存在不修改链表结构前提下的时间复杂度优化特例，需要结合实际操作的约束判断

常规操作场景下的复杂度推导 #

• 单向循环单链表的原生结构仅存储每个节点指向后继节点的单向指针，不存在反向指向的链路，也没有强制固定的全局定位锚点
• 当仅持有目标位置节点（记为p）的指针时，要找到p的前置节点，只能从链表任意节点出发，沿着后继指针逐一遍历，直到找到“后继指针指向p”的节点，整个遍历过程需要访问最多n个节点，时间开销为O(n)
• 找到前驱节点后的插入动作是固定时间操作，因此整体插入流程的时间复杂度和遍历找前驱的开销一致，为O(n)

特殊优化场景的O(1)实现 #

• 工程中有一种绕开找前驱步骤的取巧实现，全程无需遍历即可在常数时间完成操作：
  1. 新建待插入的节点，把新节点的后继指针指向目标节点p的原后继节点
  2. 把目标节点p的后继指针指向刚才新建的节点
  3. 直接交换p和新节点存储的数据值
• 这种操作本质是把“在p前面插入节点”转化为“在p后面插入节点再交换值”，整体步骤数是固定常数，时间复杂度为O(1)，但实用性有明显限制：如果节点存储的是大体积的结构体、或者业务逻辑要求两个节点的对象引用不能被交换（比如节点被其他模块持有引用），值交换的开销或业务代价会远高于遍历找前驱的成本，不适合通用场景。

常见认知偏差 #

• 不要把“维护了固定头/尾指针的循环单链表”的遍历成本和纯链表结构混淆：即使链表持有固定头指针，要找到非头节点的前驱，依然需要遍历O(n)长度的链路，除非额外用哈希表维护每个节点的前驱映射，这已经不属于原生单向循环单链表的结构范畴了。

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