从单向链表中删除节点

Question

我有这个问题：您将获得一个单向链表 L，其中 L 中的每个节点存储一个整数键，以及一个指向 L 中下一个节点的指针。最后一个节点的下一个节点设置为 NULL。您将获得一个指向存储键 k 的节点的指针 ptr，该节点不是列表中的最后一个节点。演示如何从列表中删除键 k，给定 ptr 指向包含 k 的节点的指针;你的算法应该具有时间复杂度O（1），即它应该与列表的长度无关。假设您有指向 L 的头部和尾部节点的指针。

我知道如果我们有一个双向链表，我们可以删除 O（1） 时间复杂度的节点，但是我们如何在单向链表中做到这一点呢？我们不必遍历所有列表才能找到它之前的节点吗？

Answer 1

将 A -> B ->

C -> D 视为您的链表，假设我们必须删除 B。

1. 在 ptr 和 ptr.next 之间交换数据。现在列表是 A -> C -> B -> D
2. 使 ptr.next 指向 ptr.next.next，使列表 A -> C -> D

对于边缘情况，这可能会失败。如果"ptr"是第一个节点，你只需要将头指向ptr.next。但是，如果它是最后一个节点，则无法将尾巴"移回"，因此在这种情况下，您必须遍历列表并跟踪前一个节点。

Answer 2

我知道

，如何为堆栈（LIFO）执行此操作 - 使用O（1）插入/删除

如果您不介意，该数据将是倒退的，那么您可以像第一项一样添加最后一项。

例： list.insert(1)

list.insert(2)

list.insert(3)

以常规方式将在列表中，如下所示：(1,2,3)但是如果你需要 O（1），那么它将是这样的：(3,2,1) - 那么最后一项将位于位置 1，所以删除将是这样的（Ruby 代码）

def delete
    @head = @head.next 
end