c++ - 删除仅给定节点的单向链表中间的节点。 C++

Question

在我在这里提交我的代码之前，我想知道我的想法是否正确，因为我已经给出了这个问题的“正确”答案。

是否可以通过找到给定节点的位置，然后使用常规的“在给定位置删除”功能来解决这个问题？所以基本上前一个节点将指向给定节点的下一个节点。即，如果给定 s 节点，ptr 是前一个节点，则 ptr->next = s->next。这是正确的吗？

Answer 1

你是对的。

假设要删除的节点是 delNode。

您建议的解决方案包含 2 个部分:

1. 在列表中搜索它的索引。
2. 然后删除 [index] 处的节点。

时间复杂度为 O(n) - 其中 n 是列表的大小。 (第 1 部分最坏情况是 O(n))。这个解决方案没有问题。如果找不到节点 delNode，则不会发生删除。

不同的解决方案:(及其优点和缺点)。

假设delNode前后的节点分别是A和B。A 有它的 A.data 和 A.next，delNode 有它的 delNode.data 和 delNode.next(即:delNode .next == B).删除 delNode 意味着删除后，A.next == B。

但是如果不使用搜索，我们不能更改 A.next，因为无法从 delNode(单链表)访问 A。

因此，我们可以尝试像这样操作列表，而不是搜索 delNode:delNode.data = delNode.next.data(更简单:delNode = B.data)。delNode.next = delNode.next.next (delnode.next = B.next).

这些变化将delNode对象保留在内存中，但它的状态发生了变化，B的所有内容都被复制到delNode。所以现在的delNode实际上是B，因为B.next(==C)也被复制到delNode.next，delNode之后的下一个Node是C。

之前:头部--> ... --> A --> delNode --> B --> C --> ...

after: Head--> ... --> A --> delNode(== B state includes B.next == C) --> C --> ...

所以被删除的节点实际上是B和只有B。

快速总结:

优点:

• 时间复杂度为 O(1)。

缺点:

解决方案不适用的情况:

• delNode.next == Null。
• 多态列表。对于具有多态类型的列表，存在问题。例如:Car 和Bus 都有相同的父类(super class)Vehicle，并且列表包含Vehicle 对象。如果 delNode 是 Car，B 是 Bus，那么将 B 状态复制到 delNode 的想法是错误!这些对象具有不同的具体类型，因此该解决方案不适用于这种情况。

最后一件事

C++ 实现 - 不要忘记delete(B)。