在我在这里提交我的代码之前,我想知道我的想法是否正确,因为我已经给出了这个问题的“正确”答案。
是否可以通过找到给定节点的位置,然后使用常规的“在给定位置删除”功能来解决这个问题?所以基本上前一个节点将指向给定节点的下一个节点。即,如果给定 s 节点,ptr 是前一个节点,则 ptr->next = s->next。这是正确的吗?
最佳答案
你是对的。
假设要删除的节点是 delNode。
您建议的解决方案包含 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)。
关于c++ - 删除仅给定节点的单向链表中间的节点。 C++,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29448334/