单链表的删除算法时间复杂度O(1)和O(n)

平时我们在计算单链表的第i个节点删除时间复杂度时一般认为是O(n)，过程如下

1.先从头节点开始遍历链表，找到第i-1个节点

2.将第i-1节点next指向第i个节点的next

可以看到时间主要花在了遍历链表上

如果我们已经拿到了要删除的第i个节点Node(i)，就不需要进行遍历操作和查找前驱节点了，直接拿Node(i+1)来覆盖Node(i)即可。

具体的做法如下：

1.Node(i)->data=Node(i)-next->data;

2.Node(i)-next=Node(i+1)->next;

这样的时间复杂度就是O(1)

来自 https://blog.csdn.net/JackieeeCheng/article/details/72566171