删除节点

-4

我有这样的疑问：给你一个单向链表L，其中以L存储每个节点的整数键，以及一个指向L.下一个节点的最后一个节点都有下一个节点设置为NULL。您将得到一个指针PTR到节点存储密钥K，这是不是在列表中的最后一个节点。演示如何从给定ptr的列表中删除指向包含k的节点的指针k;你的算法应该具有时间复杂度O（1），即它应该与列表的长度无关。假设你有指向L的头部和尾部节点的指针。我知道，如果我们有一个双向链表，我们可以删除O（1）时间复杂度的节点，但是我们怎样才能以单链方式清单？我们不需要遍历所有的列表来找到它之前的节点吗？删除节点

来源

2013-11-03 Hussein Hammoud

我想这是一个任务。如果是这样，不要作弊：查看课程材料，答案将很简单。这就像3行C代码，除非你在编写_you_代码时遇到_specific_问题，否则我不会给你答案。 –

这是不可能的。 – aschepler

@StefanoSanfilippo首先它不是一个任务，我有一个中期下周我正在试图解决一些额外的问题。其次，除非我有一个很艰难的时间试图解决它，我不会张贴这个问题..这些是我的想法：如果我有一个双向链表，为了删除一个指向它的节点的元素，我可以简单地执行以下操作：ptr-> previous-> next = ptr-> next;但单链表中并非如此！ –

考虑 - “乙 - ”ç - > d为您的链接列表，并让我们说，我们必须删除B. 'PTR' 指向B. PTR和PTR之间

交换数据。下一个。现在该列表是A - >Ç - >乙 - > d
化妆ptr.next指向ptr.next.next，使得列表A - >Ç - > d

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

来源

2013-11-03 16:51:53 slider

非常感谢：D它非常清楚和有用:) –

我知道如何做到这一点的栈（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

来源

2014-04-03 19:55:05 user3495403

回答

相关问题