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

Delete a node in the middle of a singly linked list given only the node. C++

在我在这里提交我的代码之前，我想知道我的想法是否正确，因为我已经 "correct" 回答了这个问题。

是否可以通过找到给定节点的位置，然后使用常规的'Delete at a given position'函数来解决这个问题？所以基本上前一个节点将指向给定节点的下一个节点。即，如果给定 s 节点，ptr 是前一个节点，则 ptr->next = s->next。这是正确的吗？

你是对的。

假设要删除的节点是 delNode.

您建议的解决方案分为两部分：

在列表中搜索其 index。
然后删除 [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 == 空。
多态列表。对于具有多态类型的列表，存在问题。例如：Car 和 Bus 都有相同的 SuperClass Vehicle，列表包含车辆对象。如果delNode是Car，B是Bus，复制B状态到delNode的思路是错误！这些对象具有不同的具体类型，因此该解决方案不适用于这种情况。

最后一件事

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

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

Delete a node in the middle of a singly linked list given only the node. C++

c++

linked-list