c - 删除单向链表中的节点

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 基本上打乱节点内容，并释放节点: Image that you get a reference to node B to be deleted in:

   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*

然后，修改下点:

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

真正释放了下面的元素，进入到最后的情况:

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