删除链接列表

Question

Qn）只给出一个指向要在单向链表中删除的节点的指针， 如何删除它？

我试图删除最后一个元素，即1但else部分进入一个无限循环 印刷垃圾值。

Original link。

int main() 
{ 
    struct Node* head = NULL; 
    push(&head, 1); 
    push(&head, 4); 
    push(&head, 6); 
    push(&head, 8); 
    print(head); 
    del_p(head->next->next->next); 
    cout << endl; 
    print(head); 
    return 0; 
} 

void del_p(struct Node* current) 
{ 
    struct Node* temp; 
    if (current->next != NULL) 
    { 
     temp = current->next; 
     current->data = temp->data; 
     current->next = temp->next; 
     free(temp); 
    } 
    else 
    { 
     free(current); 
     current = NULL; 
    } 
} 

Answer 1

您的功能的else分支尝试重新分配current至NULL。这是有问题的，因为current是本地副本传入的指针。也就是说，您不能修改原始指针的值。

这就是您接收垃圾的原因，因为您正在访问内存已被释放的节点。

您也需要一个双指针，或者最好是参考节点：

void del_p(struct Node*& current) 

Answer 2

如果你通过要删除的节点和头节点，然后你可以循环直到找到节点之前的节点被删除。然后您需要将先前节点指向要删除的节点所指向的节点，然后您可以释放要删除的节点。

void delete(struct Node* to_delete, struct Node* head) 
{ 
    // check if node to be deleted is the head 
    if (to_delete == head) 
    { 
     head = to_delete->next; 
     return; 
    } 

    // make a local copy of the head just in case as to not alter it 
    struct Node* tempHead = head; 
    while(tempHead->next != to_delete) 
    { 
     tempHead = tempHead->next; 
    } 
    tempHead->next = to_delete->next; 
    free(to_delete); 
} 

就像一个免责声明我没有测试过这个代码，但从概念上说它应该工作。

Answer 3

删除一个节点的链表将遵循以下步骤的典型算法：

• 获取一个temp指针在Head开始。
• 将您的temp移动到您要删除的节点（本例中为最后一个：temp->next == NULL）。
• 释放内存temp2。
• 将指针temp->next设置为NULL。
• 将指针返回到head。

现在，这不是唯一的算法，有很多方法可以实现这一点。下面的代码将是我的解决方案的功能del_p（如果你想删除的最后一个节点）：

void del_p(struct Node *head) 
{ 
    if (head != NULL) 
    { 
     struct Node *temp = head; 
     while (temp->next != NULL) temp = temp->next; 
     free(temp); 
    } 
} 

可以使这个代码更一般的，以使其能够删除任何节点，通过传递一个指向该节点（或价值），代码如下所示：

void del_p(struct Node **head, struct Node *delete_node) 
{ 
    if (head != NULL) 
    { 
     struct Node *temp = *head; 
     if (temp == delete_node) 
     { 
      *head = (*head)->next; 
      free(temp); 
     } 
     else 
     { 
      while (temp->next != NULL && temp->next != delete_node) 
       temp = temp->next; 
      if (temp->next != NULL && delete_node != NULL) 
      { 
       temp->next = delete_node->next; 
       free(delete_node); 
      } 
     } 
    } 
} 

希望这对你的作品，这个代码不进行测试，但告诉我，如果你有麻烦！