在单向链表中删除中间节点，且无法使用前一个节点的指针

Question

在单向链表中删除中间节点，且无法使用前一个节点的指针

cdata-structureslinked-list

41

当我们仅拥有欲删除节点的指针而非前置节点指针时，是否可能在单链表中删除中间节点？删除后，前置节点应指向被删除节点的下一个节点。

- Nitin

那是关于什么的？在我看来，这似乎是一个足够公正的问题。 - 1800 INFORMATION

10

这是一个经典的面试问题。 - Motti

这里有一个非常清晰的答案，在相关帖子上链接。 - RBT

24个回答

27

假设有这样一个结构的列表：

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

可能会有点繁琐。

- Ben Combee

+1：你不仅似乎比米哈伊尔先回答了这个问题，而且还解释了一些危险性...奇怪的是，你得到了他答案10%的投票... - Tony Delroy

11

不可能。

有一些黑科技可以模拟删除。

但是它们都不会真正删除指针所指向的节点。

如果你在列表中有外部指针指向节点，那么删除后面的节点并将其内容复制到要删除的实际节点的常见解决方案会产生副作用，此时指向后续节点的外部指针将会变得悬空。

- codaddict

5

我很欣赏这个解决方案（删除下一个节点的方法），但它并没有回答问题。如果这是实际解决方案，则正确的问题应该是“从链表中删除指针所在节点包含的值”。当然，正确的问题会给你提供解决方案的提示。目前的问题意图混淆人们（事实上也混淆了我），特别是因为面试官甚至没有提到该节点位于中间。

- Alex B

如果你问我，链表中的一个节点是通过它的数据和在列表中的位置来确定的，而不是通过它在内存中的位置来确定的，所以我认为这两个得票最高的答案是完美的解决方案。 - Neowizard

4

一种方法是在数据中插入一个空值。每当您遍历列表时，都会跟踪上一个节点。如果您发现空数据，则修复列表并转到下一个节点。

- Joe Hildebrand

4

最佳方法仍然是将下一个节点的数据复制到要删除的节点中，将该节点的下一个指针设置为下一个节点的下一个指针，并删除下一个节点。尽管存在指向要删除的节点的外部指针的问题，但这也适用于下一个节点。考虑以下链表：A->B->C->D->E->F和G->H->I->D->E->F。如果您需要删除第一个链表中的节点C，则按照上述方法，在复制内容到节点C后删除节点D。这将导致以下列表：A->B->D->E->F和G->H->I->悬空指针。如果您完全删除NODE C，则结果列表将是：A->B->D->E->F和G->H->I->D->E->F。然而，如果您要删除节点D，并使用先前的方法，则仍然存在外部指针的问题。

- Sandeep Mathias

3

最初的建议是将：

a -> b -> c

转换为：

a ->, c

如果您保留信息，比如从节点地址到下一个节点地址的映射，则可以在下一次遍历列表时修复链。如果需要在下一次遍历之前删除多个项，则需要跟踪删除顺序（即更改列表）。

标准解决方案是考虑其他数据结构，比如跳表。

- Allan Wind

3

也许可以进行软删除？（即在节点上设置一个“已删除”标志）。如果需要，稍后可以清理列表。

- perimosocordiae

1

然而，一个问题是维护该标志将增加每个项目的内存。 - Arafangion

1

如果您想保持列表的可遍历性，就不能这样做。您需要更新前一个节点以链接到下一个节点。

你怎么会陷入这种情况呢？你在尝试做什么让你问这个问题？

- Allen

1

你必须顺着链表向下遍历寻找前一个节点。这会使得删除操作的时间复杂度变为O(n**2)。如果你是唯一进行删除操作的代码，实践中你可以通过缓存前一个节点并从那里开始搜索来提高效率。但是否能带来好处取决于删除操作的模式。

- Kimbo

遍历列表仍然需要O(n)的时间复杂度来删除一个元素。 - Dave L.

确实。我是指删除整个列表（随机地）。 - Kimbo

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mikhail Tatarnikov · Accepted Answer

这肯定更像是一道问答题而不是一个真正的问题。但是，如果我们允许做一些假设，它可以在O(1)时间内解决。为了实现这一点，列表指向的结构必须是可复制的。算法如下：

我们有一个类似于以下结构的列表: ... -> Node(i-1) -> Node(i) -> Node(i+1) -> ...，我们需要删除Node(i)。

将数据（而不是指针本身）从Node(i+1)复制到Node(i)，列表将变为: ... -> Node(i-1) -> Node(i+1) -> Node(i+1) -> ...
将第二个Node(i+1)的NEXT值复制到一个临时变量中。
现在删除第二个Node(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;
}

迈克。