书山有路勤为径
把下一个节点的数据拷贝到目标节点,然后删除下一个节点,即可实现 O(1) 的节点删除。
不过,如果目标节点是尾节点,就没有下一个节点可以借用,删除操作仍然需要从头遍历,时间复杂度退化为 O(n)。
综合来看,平均情况下的时间复杂度还是 O(1)。