仅指定指向该节点的指针时，从单个链表中删除任何节点

6 回答

• 1

  悬挂指针：

  （http://en.wikipedia.org/wiki/Dangling_reference）计算机编程中的悬空指针和野指针是指向不指向适当类型的有效对象的指针 . 这些都是违反记忆安全的特殊情况 . 删除或取消分配对象时会出现悬空指针，而不修改指针的值，因此指针仍然指向解除分配的内存的内存位置 . 由于系统可以将先前释放的存储器重新分配给另一个进程，如果原始程序然后取消引用（现在）悬空指针，则可能导致不可预测的行为，因为存储器现在可能包含完全不同的数据 .

  在您的回答中，要删除给定节点，您实际上删除了可能被指针引用的 next 节点 . 这就是悬垂指针问题出现的原因 .

  （1）正如您在备注中说明的那样，没有外部参考列表 . （2）面试官说，可能会出现悬垂指针问题 .

  （1）和（2）都不能同时正确 . 这意味着某处存在误解 .

  关于删除最后一个节点：

  但是面试官再次问我，如果我传递最后一个节点的地址怎么办？我告诉他，因为下一个将是一个NULL，将NULL复制到数据字段以及下一个节点的地址也是NULL .

  我认为你混淆了这两件事：（1）指向NULL的指针p，（2）在其数据字段中具有NULL的链表节点 .

  假设数据结构是 a -> b -> c -> d . 将NULL写入d's数据字段不会使c在其 next 字段中具有NULL指针 .

  您可以删除永远不会删除的最后一个节点 if the linked list always has a special last node . 例如， a -> b -> c -> d -> LAST 其中LAST在其数据字段中有一个特殊值，表示它实际上是最后一个元素 . 现在要删除d，你可以删除LAST并在d's数据字段中写入特殊值 .

  也许这些正是你在面试中试图说的，在这种情况下，你和面试官之间肯定会有一些误解 .

  回复于 2024-05-03T22:47:33+08:00
• 3

  脚步：

  • 将数据从节点（i 1）复制到节点（i）

  • 将第二个节点（i 1）的NEXT复制到临时变量中 .

  • 现在删除第二个节点（i 1）//它不需要指向前一个节点的指针 .

  功能：

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

  回复于 2024-05-03T22:47:33+08:00
• 0

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

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

  回复于 2024-05-03T22:47:33+08:00
• 9

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

  仅当数据结构使用特定的"last node"元素进行扩充时，您的解决方案才能使用最后一个节点 . （如果你使用的是Smalltalk，你可以写 self become: nil 没有其他语言有类似的东西）

  不，如果列表有外部引用，则没有通用解决方案 . 我认为面试官想知道你是否真的在这个主题上是知识渊博的，或者只是重复一个记忆回答 .

  回复于 2024-05-03T22:47:33+08:00
• 2

  可能你的链接列表遍历可能需要假设任何指向 null 的节点都是 null 节点，无论值是什么......

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

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

  回复于 2024-05-03T22:47:33+08:00
• 12

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

  回复于 2024-05-03T22:47:33+08:00