我有这个问题：给你一个单链表L，其中L中的每个节点存储一个整数键，以及指向L中下一个节点的指针 . 最后一个节点将其下一个节点设置为NULL . 您将获得指向存储密钥k的节点的指针ptr，该密钥不是列表中的最后一个节点 . 显示如何从给定ptr指向包含k的节点的指针的列表中删除密钥k;你的算法应该具有时间复杂度O（1），即它应该与列表的长度无关 . 假设你有指向L的头部和尾部节点的指针 .
我知道，如果我们有一个双向链表，我们可以删除O（1）时间复杂度的节点，但我们怎么能在单链表中做呢？难道我们不必迭代所有列表才能在它之前找到节点吗？
2 回答
考虑A - > B - > C - > D作为你的链表，让我们说我们必须删除B.'ptr'指向B.
在ptr和ptr.next之间交换数据 . 现在列表是A - > C - > B - > D.
使ptr.next指向ptr.next.next，使列表A - > C - > D
对于边缘情况，这可能会失败 . 如果'ptr'是第一个节点，你只需要指向ptr.next . 但如果它是最后一个节点，则不能将尾部“后退”，因此在这种情况下，您必须遍历列表并跟踪前一个节点 .
我知道，如何为Stack（LIFO）做 - 用 O(1) 插入/删除
如果你不介意，那些数据将会倒退，那么你可以像第一个一样添加最后一项 .
示例：list.insert（1）
list.insert（2）
list.insert（3）
在常规方式将在这样的列表中：
(1,2,3)但如果你需要 O(1) 那么它将是这样的：(3,2,1)- 然后最后一项将在位置1，所以删除将是这样的（红宝石代码）def删除
@head = @head.next
结束