-3

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

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

4

2 回答 2

4

考虑 A -> B -> C -> D 作为您的链表，假设我们必须删除 B。'ptr' 指向 B。

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

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

于 2013-11-03T16:51:53.673 回答
0

我知道，如何为 Stack (LIFO) 执行此操作 - 使用O(1)插入/删除

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

例子： list.insert(1)

list.insert(2)

list.insert(3)

以常规方式将在这样的列表中：(1,2,3) 但是如果您需要O(1)那么它将是这样的：(3,2,1)-那么最后一项将在位置 1，因此删除将是这样的（红宝石代码）

def delete
    @head = @head.next 
end

于 2014-04-03T19:55:05.327 回答