删除单链接列表中的节点

Question

如何删除单链接列表中的节点,只有一个指针指向要删除的节点？

[开始和结束指针未知,可用信息是指向应删除的节点的指针]

Answer 1

您可以删除节点而不获取上一个节点,方法是让它模仿以下节点并删除该节点:

void delete(Node *n) {
  if (!is_sentinel(n->next)) {
    n->content = n->next->content;
    Node *next = n->next;
    n->next = n->next->next;
    free(next);
  } else {
    n->content = NULL;
    free(n->next);
    n->next = NULL;
  }
}

如您所见,您需要专门处理最后一个元素.我使用的是一种特殊的节点作为前哨淋巴结,以纪念它具有结局content和next是NULL.

更新:这些行Node *next = n->next; n->next = n->next->next基本上是对节点内容进行洗牌,并释放节点:您在以下位置获取对节点B的引用的图像:

   A           / To be deleted
  next   --->  B
              next  --->    C
                           next ---> *sentinel*

第一步是n->content = n->next->content:将以下节点的内容复制到要"删除"的节点:

   A           / To be deleted
  next   --->  C
              next  --->    C
                           next ---> *sentinel*

然后,修改next点数:

   A           / To be deleted
  next   --->  C       /----------------
              next  ---|    C          |
                           next ---> *sentinel*

实际上释放了以下元素,进入最后的案例:

   A           / To be deleted
  next   --->  C
              next  --->    *sentinel*

Answer 2

不可能.

有些黑客可以模仿删除.

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

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

你可以在这里找到关于SO的一些讨论.