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

Question

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

Answer 1

这绝对是一个测验,而不是一个真正的问题.但是,如果允许我们做出一些假设,可以在O(1)时间内解决.要做到这一点,列表指向的限制必须是可复制的.算法如下:

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

1. 将数据(不是指针,数据本身)从节点(i + 1)复制到节点(i),列表将如下所示:... - >节点(i-1) - >节点(i + 1) - >节点(i + 1) - > ...
2. 将第二个节点(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;
}

麦克风.

Answer 2

让我们假设一个结构列表

A - > B - > C - > D.

如果你只有一个指向B的指针并希望删除它,你可以做类似的事情

tempList = B->next;
*B = *tempList;
free(tempList);

然后列表看起来像

A - > B - > D.

但是B会保留C的旧内容,有效地删除B中的内容.如果其他一段代码持有指向C的指针,这将无效.如果你试图删除节点D,它也行不通.如果你想进行这种操作,你需要使用一个没有真正使用的虚尾节点来构建列表,这样你就可以保证没有有用的节点会有一个NULL的下一个指针.对于存储在节点中的数据量很小的列表,这也更有效.像一个结构

struct List { struct List *next; MyData *data; };

没关系,但是就是这样

struct HeavyList { struct HeavyList *next; char data[8192]; };

会有点累赘.

Answer 3

不可能.

有些黑客可以模仿删除.

但是,实际上没有一个会删除指针所指向的节点.

如果外部指针指向列表中的节点,则删除以下节点并将其内容复制到要删除的实际节点的流行解决方案会产生副作用,在这种情况下,指向后续节点的外部指针将变为悬空.

Answer 4

我很欣赏这个解决方案的独创性(删除下一个节点),但它没有回答问题的问题.如果这是实际的解决方案,那么正确的问题应该是"从链接列表中删除指定给定指针的节点中包含的VALUE".但是,当然,正确的问题可以为您提供解决方案的提示.制定这个问题的目的是让人感到困惑(实际上这件事发生在我身上,特别是因为面试官甚至没有提到节点位于中间).

Answer 5

是的，但你无法解除它的链接。如果您不关心损坏内存，请继续;-)