c - 当指向前一个节点的指针不可用时从单个链表中删除中间节点

Question

当我们唯一可用的信息是指向要删除的节点的指针而不是指向前一个节点的指针时，是否可以删除单链表中的中间节点？删除后，前一个节点应指向已删除节点旁边的节点。

Answer 1

这绝对更像是一个测验，而不是一个真正的问题。但是，如果允许我们做一些假设，它可以在 O(1) 时间内解决。为此，列表指向的限制必须是可复制的。算法如下:

我们有一个如下所示的列表:... -> Node(i-1) -> Node(i) -> Node(i+1) -> ... 我们需要删除 Node(i)。

1. 将数据(不是指针，数据本身)从 Node(i+1) 复制到 Node(i)，列表如下所示: ... -> Node(i-1) -> Node(i+1 ) -> 节点(i+1) -> ...
2. 将第二个 Node(i+1) 的 NEXT 复制到一个临时变量中。
3. 现在删除第二个节点(i+1)，它不需要指向前一个节点的指针。

伪代码:

void delete_node(Node* pNode)
{
    pNode->Data = pNode->Next->Data;  // Assume that SData::operator=(SData&) exists.
    Node* pTemp = pNode->Next->Next;
    delete(pNode->Next);
    pNode->Next = pTemp;
}

迈克。