当指向前一个节点的指针不可用时，从单个链表中删除中间节点 [英] Deleting a middle node from a single linked list when pointer to the previous node is not available

问题描述

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

Is it possible to delete a middle node in the single linked list when the only information available we have is the pointer to the node to be deleted and not the pointer to the previous node?After deletion the previous node should point to the node next to deleted node.

推荐答案

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

It's definitely more a quiz rather than a real problem. However, if we are allowed to make some assumption, it can be solved in O(1) time. To do it, the strictures the list points to must be copyable. The algorithm is as the following:

我们有一个看起来像这样的列表:... -> Node(i-1) -> Node(i) -> Node(i+1) -> ... 我们需要删除 Node(i).

We have a list looking like: ... -> Node(i-1) -> Node(i) -> Node(i+1) -> ... and we need to delete 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;
}

迈克.

这篇关于当指向前一个节点的指针不可用时，从单个链表中删除中间节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！