单链表不同插入场景的时间复杂度分析及疑问

先纠正一个关键认知：你认为两种场景时间复杂度都是O(n)的结论并不准确——允许修改第i个节点地址/内容的情况下，时间复杂度可以做到O(1)，而地址不可改时则必须是O(n)。下面具体分析两种场景的差异：

场景1：第i个节点地址不可更改 #

这是单链表插入的标准操作逻辑：

• 要在i-1和i节点之间插入新节点，必须让i-1节点的指针指向新节点，同时新节点的指针指向i节点。但单链表没有反向指针，已知i节点的地址无法直接定位其前驱i-1节点，必须从头遍历整个链表，直到找到指针域等于i节点地址的节点（也就是i-1），这一步的时间开销是O(n)。
• 后续操作：创建新节点，设置新节点的next为i节点地址，修改i-1节点的next为新节点地址，这两步都是O(1)。
• 核心影响：
  • 完全保留原i节点的地址和身份，所有外部对i节点的引用依然有效，不会出现逻辑错误。
  • 操作符合单链表的常规设计，逻辑清晰，易于维护和调试。

场景2：允许第i个节点地址/内容更改 #

这种情况下可以采用「偷梁换柱」的技巧，跳过寻找前驱节点的步骤：

• 操作步骤：
  1. 创建新节点，将原i节点的数据域和next指针全部复制到这个新节点中。
  2. 修改原i节点的数据域为要插入的新数据，同时将原i节点的next指针指向刚创建的新节点。
• 此时原i-1节点的next依然指向原i节点的地址，但原i节点已经变成了我们要插入的新节点，新创建的节点则是原来的i节点——相当于完成了在i-1和原i节点之间插入新节点的需求。
• 核心差异与影响：
  1. 时间复杂度骤降：不需要遍历找前驱，整体时间复杂度为O(1)，这是最核心的优势。
  2. 外部引用失效：如果之前有其他变量保存了原i节点的地址，现在这个地址指向的是插入的新节点，而非原来的i节点，会导致依赖原i节点的逻辑出错。
  3. 节点身份混淆：原i节点的地址被复用成了新节点的地址，在调试、日志追踪或需要区分节点身份的场景中，容易造成混淆。
  4. 可读性差：操作逻辑偏「取巧」，不如标准插入逻辑直观，团队协作时可能增加理解成本。

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