删除单链接列表中的节点 [英] Delete a node in singly link list

问题描述

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

How to delete a node in a singly link list with only one pointer pointing to node to be deleted?

[开始和结束指针不知道，可用信息是指向应该被删除的节点的指针]

[Start and end pointers are not known, the available information is pointer to node which should be deleted]

推荐答案

您可以删除没有获取上一个节点的节点，以下节点并删除该节点：

You can delete a node without getting the previous node, by having it mimic the following node and deleting that one instead:

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

如您所见，您需要特别处理为最后一个元素。我正在使用一个特殊节点作为哨兵节点来标记具有内容和下一个的结局为 NULL 。

As you can see, you will need to deal specially for the last element. I'm using a special node as a sentinel node to mark the ending which has content and next be NULL.

更新：行 Node * next = n-> next; n-> next = n-> next-> next 基本上洗涤节点内容，并释放节点：Image，您将获得对要删除的节点B的引用：

UPDATE: the lines Node *next = n->next; n->next = n->next->next basically shuffles the node content, and frees the node: 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 ：将以下节点的内容复制到要删除的节点：

The first step is n->content = n->next->content: copy the content of the following node to the node to be "deleted":

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

然后，修改下一个点：

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

实际上释放了以下元素，得到最终的案例：

The actually free the following element, getting to the final case:

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

这篇关于删除单链接列表中的节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！