当仅给出指向该节点的指针时，从单个链表中删除该节点

Question

这是我在采访中被问到的一个问题。

“内存中有一个单链表。你要删除一个节点。你需要编写一个函数来删除该节点，该函数只需要删除节点的地址作为输入，而不需要其他任何东西（包括头）”

我给出的答案类似于下面帖子中的答案——将下一个节点的内容复制到要删除的节点并删除下一个节点。

删除当指向前一个节点的指针不可用时，单链表的中间节点

但是面试官又问我，如果我传递最后一个节点的地址怎么办？我告诉他，由于下一个节点将为 NULL，因此将该 NULL 连同下一个节点的地址复制到数据字段中，该节点也是 NULL。然后他告诉我会有一个悬空指针的问题......我有点不明白。有人可以解释一下这个问题吗？有一个通用的解决方案吗？

更新（两天后）：一点补充。考虑到链表末尾没有特殊节点。最后一个节点指向 NULL，如果该节点作为输入给出，如何使前一个节点指向 NULL。或者说这是不可能的？

简单地说：如果一个节点作为函数的输入，如何使引用它的指针指向 NULL

Answer 1

步骤：

1. 将数据从 Node(i+1) 复制到 Node(i)
2. 将第二个 Node(i+1) 的 NEXT 复制到临时变量中。
3. 现在删除第二个节点(i+1) // 它不需要指向前一个节点的指针。

功能：

void delete_node(node* node)
{
    node->Data = node->Next->Data;
    node* temp = node->Next->Next;
    delete(node->Next);
    node->Next = temp;
}

Answer 2

悬空指针：

（http://en.wikipedia.org/wiki/Dangling_reference）

计算机编程中的悬空指针和野指针是
不指向适当类型的有效对象的指针。
这些是内存安全违规的特殊情况。

当对象被删除或释放时，就会出现悬空指针，
不修改指针的值，使指针仍然
指向已释放内存的内存位置。由于系统
可能会将先前释放的内存重新分配给另一个进程，如果
然后原始程序取消引用（现在）悬空指针，
可能会导致不可预测的行为，因为内存现在可能包含
完全不同的数据。

在您的答案中，要删除给定节点，您实际上删除了下一个节点，该节点可能由指针引用。这就是悬空指针问题的产生方式。

(1) 正如您在注释中所澄清的那样，该列表没有外部引用。
(2) 正如面试官所说，会出现悬空指针问题。

(1)和(2)不可能同时正确。这意味着某处存在误解。

关于删除最后一个节点：

但是面试官又问我，如果我传了对方的地址怎么办？
最后一个节点。我告诉他，因为下一个将是NULL，所以复制那个NULL
与下一个节点的地址一起进入数据字段
也为 NULL。

我认为您混淆了这两件事：（1）指向 NULL 的指针 p，（2）数据字段中包含 NULL 的链表节点。

假设数据结构为a -> b-> c-> d。将 NULL 写入 d 的数据字段不会神奇地使 c 在其 next 字段中拥有 NULL 指针。

如果链表总是有一个永远不会被删除的特殊最后一个节点，您可以删除最后一个节点。例如，a -> b-> c-> d-> LAST 其中 LAST 在其数据字段中有一个特殊值，表示它确实是最后一个元素。现在要删除 d，您可以删除 LAST 并将特殊值写入 d 的数据字段。

也许这些正是你在面试时试图讲述的内容，在这种情况下，你和面试官之间一定存在一些沟通不畅。

Answer 3

然后应该在程序中检查给定节点是否是最后一个节点。

void delete_node(node* node1) {
    node* search=head;
    if(node1==head) {
        head=head->next;
        search->next=NULL;
        node1->next=NULL;
    }
    while(search->next != node1)
        search=search->next;
    if(node1->next==NULL) {
       search->next=NULL;
    } else {
       search->next=node1->next;
       node1->next=NULL;
    }
    delete node1;
}

Answer 4

如果还有其他元素指向下一个节点，这些元素将被复制到当前节点然后被删除，那么此操作将引入错误。因此，在您的回答中，您应该强调您的解决方案仅在没有对该列表的外部引用的情况下才有效。

仅当数据结构使用特定的“最后一个节点”元素进行扩充时，您的解决方案才适用于最后一个节点。 （如果您使用的是 Smalltalk，则可以编写 self come: nil 没有其他语言有类似的内容）

不，如果存在对该列表的外部引用，则没有通用解决方案。我认为面试官想看看你是否真的对这个主题很了解，或者只是在重复记住的答案。

Answer 5

也许您的链接列表遍历可能需要假设任何指向 null 的节点都是 null 节点，无论其值如何......

a->b->c->d->NULL

所以 d 是null 节点并且该节点不应被视为节点。这样您就可以节省使用特殊值的时间，因为它们在一般意义上是不正确的。除此之外，您将没有任何其他方式让前一个节点指向 null。

Answer 6

当给出最后一个节点时，不是将其删除，而是将其分配给虚拟节点，并且在显示数据时，我们可以检查 ptr->next 作为虚拟节点并在那里终止。

对于悬空指针，我相信当指针被释放（释放）时，它将成为悬空指针，因此在释放后将其分配为 NULL。

下面是我针对这个问题的代码片段：

dummy-> data = NULL;
dummy-> next = NULL;
FUNC(del_ptr)
{
if (del_ptr->next == NULL )
{
del_ptr = dummy;
return;
}
struct node *next = del_ptr ->next;
del_ptr -> data = next -> data;
del_ptr -> next = next -> next;
free(next);
next=NULL;
}

Answer 7

假设：deleteNode() 引用节点指针。

没有 while 循环的简单解决方案。在deleteNode()中，if case处理头节点和中间节点的删除，else处理最后一个节点的删除。

#include <iostream>
using namespace std;

class Node{

public:
  int data;
  Node* next;

  Node(int d): data(d){}
};

void insert(Node* &head,  int data){
  Node *node = new Node(data);
  node->next = head;
  head = node;
}

void print(Node *head){
  Node *temp = head;
  while(temp !=NULL){
    cout << temp->data <<" ";
    temp = temp->next;
  }
  cout << endl;
}

void deleteNode(Node *&node){

  cout << "Deleting "<<node->data<<endl;
  if(node->next != NULL){
    Node *t = node->next;
    node->data = node->next->data;
    node->next = node->next->next;

    delete t;
  }else{
    delete node;
    node = NULL;
  }
}

int main(int argc, char const *argv[]) {

  Node *head = NULL;
  insert(head, 10);
  insert(head, 20);
  insert(head, 30);
  insert(head, 40);
  insert(head, 50);

  print(head);

  deleteNode(head->next); //delete 40
  deleteNode(head->next->next->next); //delete last node 10

  print(head);

  return 0;
}

Answer 8

public void removeNode(Node node){
    /* if no node return null */
    if(node==null) return;

    /* if only 1 node then delete node */
    if(node.getNext()==null) {
        node = null;
        return ;
    }

    /* copy next node data to this node */
    node.data = node.getNext().data();

    /* store the next next node */
    Node second = node.getNext().getNext();

    /* remove next node */
    removeNode(node.getNext());

    /* set the copied node as next */
    node.setNext(second);
}