仅使用 1 个本地指针删除链表中的节点

Question

K.N King 的《C 编程：一种现代方法》一书的练习摘录。如果我的解决方案的最后一部分不正确，我会寻求帮助。

修改 delete_from_list 函数，使其只使用一个指针变量，而不是两个（cur 和 prev）。

这是一个简单的链表，函数删除遇到的第一个节点，其

.value

等于参数

n

。

原码：

struct node {
    int value;
    struct node *next;
};

struct node *delete_from_list(struct node *list, int n)
{
    struct node *cur, *prev;

    for (cur = list, prev = NULL;
         cur != NULL && cur->value != n;
         prev = cur, cur = cur->next)
        ;
    if (cur == NULL)
        return list;
    if (prev == NULL)
        list = list->next;
    else
        prev->next = cur->next;
    free(cur);
    return list;
}

我的解决方案：

struct node *delete_from_list(struct node **list, int n) {
    struct node *ptr = *list;
    while (ptr != NULL) {
        if (ptr->value == n) {
            *list = ptr->next;
            free(ptr);
            break;
        }
        list = &(ptr->next);
        ptr = ptr->next;
    }
    return *list;
}

我认为这个解决方案几乎是正确的，但我很难理解最后一个语句

return *list;

是否实际上返回了列表的开头。这是我第一次使用指向结构指针的指针，所以我可能误解了一些概念。

比起完全不同的解决方案，我更想知道我的解决方案是否正确，以节省您的时间。

Answer 1

您将

list

参数更改为指向

node*

变量的指针，该变量指向链表的头部

node

。这种变化本身很好（但不是练习的一部分，仅供参考）。

通过使用指向指针的指针作为输入参数，不再有任何理由

return

node*

指向列表头的指针，因为您只需修改输入

node*

变量以指向新的列出负责人，如果需要的话。

如果您的循环在列表中找到

n

值，则您正在尝试执行该更新。但是，您正在修改输入

node*

变量 unconditionally 现在指向下一个

node

，它跟随

node

被删除。您必须仅在从列表中删除头部

node

时才执行该更新。否则，您将失去对已删除

node

之前的

node

的访问权限，从而破坏您的列表。您没有像原始代码那样执行该检查。

所以，尝试更像这样的东西：

struct node* free_node(struct node *n)
{
    struct node *next = n->next;
    free(n);
    return next;
}

/* alternatively:
void free_node(struct node **n)
{
    struct node *next = (*n)->next;
    free(*n);
    *n = next;
}
*/

void delete_from_list(struct node **list, int n) {
    while (*list != NULL) {
        if ((*list)->value == n) {
            *list = free_node(*list);
            // or: free_node(list);
            break;
        }
        list = &((*list)->next);
    }
}

在第一次循环迭代中，

list

指向调用者的

node*

变量，该变量指向列表。如果第一个

node

被删除，调用者的

node*

变量被更新为指向被删除的节点之后的下一个

node

，函数退出。

否则，在下一次循环迭代中，

list

现在指向前一个

node

的

next

字段。如果下一个

node

被删除，前一个

node

的

next

字段将更新为指向下一个

node

跟随被删除的

node

，并且函数退出。

重复最后一步，直到遍历整个列表。

---

现在，如果更改

delete_from_list()

函数的签名不是一个选项（因为练习没有要求您这样做），那么您可以改为这样做，效果相同：

struct node* delete_from_list(struct node *list, int n) {
    struct node **ptr = &list;
    while (*ptr != NULL) {
        if ((*ptr)->value == n) {
            *ptr = free_node(*ptr);
            // or: free_node(ptr);
            break;
        }
        ptr = &((*ptr)->next);
    }
    return list;
}