我对哪个选项是正确的以及为什么感到困惑。所以这里是问题:
我真的很困惑这个话题,如果有人可以修改我的解决方案并理解为什么他们的解决方案是正确的,那么我会很感激。谢谢。
首先你是对的。为了删除最后一个元素,你需要遍历列表并修改指针,因此它是Ω(n)。
然而在第二个中它是O(1)。堆栈是LIFO。你有一个指向堆栈头部的指针。您需要做的就是为新元素创建一个节点,使其成为当前头部的下一个节点,并将头部设置为新创建的元素。因此,操作的数量不是堆栈大小的函数。它可以在恒定时间内完成,即O(1)。
编辑:上面的答案假设数据结构没有实现一些数组实现,由于调整大小可能再次为O(n)。