删除LinkedList节点的正确方法是什么？

Question

我已经在C中创建了一个链表。现在我想从任何位置删除节点，例如第一个节点或最后一个节点或任何第n个节点。我写了一段运行良好的代码。但问题是有人告诉我虽然它给出了正确的输出但代码是错误的。这是代码。

删除第一个节点：

struct node {
int number;
struct node *next;
};
struct node *head = NULL;
struct node *tail = NULL;

void deletefirst(struct node *a) {
head = head->next;
free(a);
}

现在使用这段代码我得到了我想要的输出。问题是我的朋友告诉我头指针不是通过引用传递的。 *a 持有一份副本。它打印正确是因为 head=head->next 因为 head 是全局声明的。但是 free(a) 不会从 head 中删除原始节点，它只释放 a 的副本。然后他给了我他的代码

void deletefirst(struct node **a) {
struct node *temp = *a;
*a = (*a)->next;
free(temp);
}

根据他的说法，这里的 head 是通过引用传递的，因此这段代码能够从 head 中释放原始节点。我的问题是，我的正确、他的正确还是两者都正确？如果他真的是正确的，那么我的另一个带有 *a 的代码如何删除最后一个节点？

删除最后一个节点

void deletelast(struct node *a) {
   while (a->next->next != NULL) {
      a = a->next;
   }
   free(a->next);
   a->next = NULL;
}

这是我删除最后一个节点的代码。在他看来这也是错误的吗？我的意思是我将 *a 指向 head 所以它一定是正确的。如果能简单解释一下就更好了。另一件事是，如果我的代码 *a 是错误的，而他是正确的，我们需要通过引用传递 **a 那么当我创建插入函数 *a 时，他们也可以找到。我对指针有一些基础知识，但没有那么高级。

这是我要插入到最后的代码 （这里使用了另一种结构而不是上面的结构）

void llinsertend(const char *a, const int *b) {
struct node *current = malloc(sizeof(struct node));
if (current == NULL) {
printf("Current creation failed.\n");
}
current->name = malloc(strlen(a) + 1);
if (current->name == NULL) {
printf("String allocation failed\n");
}
strcpy(current->name, a);
current->age = *b;
current->next = NULL;
if (linkeslist1head == NULL) {
linkeslist1head = current;
linkedlist1tail = current;
} else {
linkedlist1tail->next = current;
linkedlist1tail = current;
}
}

如果在我的删除函数中，如果 *a 无法修改我的第一个原始头链表或删除节点，那么在插入函数中，*a 如何能够修改原始头函数。我还使用了chatgpt，它在删除功能中告诉我我错了，因为它保存了副本并且无法删除原始头节点，而我朋友的代码是正确的。

Answer 1

这两个功能

deletefirst

你和你的朋友

void deletefirst(struct node *a) {
head = head->next;
free(a);
}

和

void deletefirst(struct node **a) {
struct node *temp = *a;
*a = (*a)->next;
free(temp);
}

只是没有意义是不正确的，并且可能会调用未定义的行为。

首先，如果您的函数处理函数内使用的文件作用域变量

head

，则将任何指向节点的指针传递给函数没有意义。

在这两个函数中，不检查传递的指针或通过引用传递的指针是否为空指针。因此取消引用空指针会调用未定义的行为。此外，如果需要，这些函数不会更新列表定义中使用的指针

tail 

。

如果您使用文件范围指针

head

和

tail

那么该函数可以如下所示

void deletefirst( void ) 
{
    if ( head != NULL )
    {
        struct node *first = head;
        head = head->next'
        free( first );
        
        if ( head == NULL ) tail = NULL;
    }
}

至于你朋友的函数，那么他还需要通过引用将指针

tail

传递给函数，并与上面所示的函数类似地定义函数。

但这使得代码变得更加复杂。最好再引入一种结构，该结构将在其内部包含这些指针

head

和

tail

作为 ots 数据成员。

您的函数

deletelast

与您的函数

deletefirst

存在相同的问题。它可以这样定义

void deletelast( void ) 
{
    if ( head != NULL )
    {
        if ( head->next == NULL )
        {
            deletefirst();
        }
        else
        {
            struct node *current = head;
            while ( current->next->next != NULL )
            {
                current = current->next;
            }

            struct node *last = current->next;
            current->next = last->next;
            free( last );         
            tail = current;
        }
    }
}

但正如我已经指出的那样，使用全局变量是一个坏主意。引入一个额外的结构会更好，因为我已经在块作用域中描述并使用了该结构的对象。