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

问题描述

是否可以删除单链表的中间节点时，可用我们的唯一信息是指向该节点将被删除，而不是指向previous节点？删除了$ P $之后pvious节点应该指向旁边的删除节点的节点。

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:

我们有一个看起来像列表：... - >节点（i-1） - >节点（i） - >节点（i + 1） - > ...我们需要删除节点（i）。

We have a list looking like: ... -> Node(i-1) -> Node(i) -> Node(i+1) -> ... and we need to delete Node(i).

1. 复制数据（不是指针，数据本身）的节点（i + 1）到节点（i），列表将类似于：... - >节点（i-1） - >节点（i + 1 ） - >节点（i + 1） - > ...


2. 复制第二个节点的下一个第（i + 1）插入一个临时变量。


3. 现在，删除所述第二节点第（i + 1），它不需要指针previous节点

伪code：

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;
}

麦克。

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