在 C++ 中删除链表中第 n 个位置的节点 ------ 最后一个数字没有被删除

Question

在运行这段代码中，当我输入 n 作为 4 时，程序停止而不是输出 2 4 6 我无法删除此链表中的最后一个节点。它适用于所有其他位置但不适用于最后一个节点。是不是因为第(n-1)个节点应该指向的最后一个节点之后没有第(n+1)个节点。我是否应该在删除函数中显式添加更多代码以删除最后一个节点？


#include<stdio.h>
#include<stdlib.h>
struct Node{
    int data;
    struct Node* next;
};
struct Node* head;
void Insert(int data, int n)
{
    struct Node* temp1 = new Node();
    temp1->data = data;
    temp1->next = NULL;
    if(n == 1)
    {
        temp1->next = head;
        head = temp1;
        return;
    
    }
    struct Node* temp2 = head;
    for(int i = 0; i<n-2; i++)
    {
        temp2 = temp2->next;
    }
    temp1->next =temp2->next;
    temp2->next = temp1;
}
void Print()
{
    struct Node* temp = head;
    while(temp != NULL)
    {
        printf("%d\n", temp->data);
        temp = temp->next;
    }
    printf("\n");
}
void Delete(int n)
{
    struct Node* temp1 = head;
    if(n == 1)
    {
       head = temp1->next;
       free(temp1);
       return;
    }
int i;
    for(i = 0; i<n-2; i++)
      {
         temp1 = temp1->next; 
         struct Node* temp2 = temp1->next;
         temp1->next = temp2->next;
         free(temp2);
      }
  }
int main()
{
    head = NULL;
    Insert(2, 1);
    Insert(4,2);
    Insert(6,3);
    Insert(5,4);
    Print(); 
    int n;
    printf("Enter a position\n");
    scanf("%d", &n);
    printf("\n");
    Delete(n);
    Print();
}

Answer 1

看来您需要对删除算法做更多的工作。如果你把你的测试用例扩展到超过 4 个节点，我想你会发现除了删除最后一个节点之外还有更多的问题。我重写了你的删除函数，同时试图保留你的一些相同逻辑。

评论提到了您的一些问题，但看起来您的 for 循环调用免费 n-2 次。那不是我们想要的。我们使用循环“找到”我们要删除的节点，然后调用 free 一次（在重新分配适当的指针之后）

void Delete(int n){
    struct Node* temp1 = head;
    if(n == 1)
    {
        head = temp1->next;
        free(temp1);
        return;
    }

    // Find the node right before the one you want to delete. 
    for(int i = 0; i<n-2; i++){
         temp1 = temp1->next; 
    }

    struct Node* node_to_be_deleted = temp1->next;
    temp1->next = node_to_be_deleted->next;

    free(node_to_be_deleted);
}

注意：这里没有错误检查...

在 C++ 中删除链表中第 n 个位置的节点 ------ 最后一个数字没有被删除

Deleting a node at nth position in a linked list in C++ ------ Last number is not getting deleted

c++

linked-list