删除单向链表中的一个节点 [英] 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;
  }
}

如您所见，您需要专门处理最后一个元素.我使用一个特殊节点作为哨兵节点来标记具有 content 和 next 为 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 基本上打乱了节点内容，并释放了节点: 您获得对要删除的节点 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*

然后，修改next点:

   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屋！