C 删除链表中的节点

Question

我有这个程序，它具有创建列表的功能，如果节点的值等于函数 delete_node() 的参数 x 则删除节点，然后打印链表节点。创建和打印工作正常，但我无法删除值为 x 的节点。我得到原始列表或空白列表。

#include <stdio.h>

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

struct list *create_list(struct list *l, int x) {

    //allocate memory for new tmp node
    struct list *tmp = malloc(sizeof(struct list));

    tmp->value = x;

    //tmp shtohet ne koke te listes
    tmp->next = l;

    //l behet koka e listes
    l = tmp;

    return l;
}

struct list *delete_node(struct list *l, int x) {

    while (l) {
        if (l->value == x) {
            //printf("%d", x);
            struct list *tmp = malloc(sizeof(struct list));

            tmp->value = l->next->value;
            tmp->next = l->next->next;
            l = tmp;

            printf("%d ", tmp->value);

        }

        l = l->next;
    }

    return l;
}

int main() {

    struct list *l = NULL;

    for (int i = 5; i > -6; --i)
        l = create_list(l, i);

    l = delete_node(l, 3);

    while (l) {
        printf("%d ", l->value);
        l = l->next;
    }

    printf("\n");

    return 0;
}

Answer 1

这是对有问题的代码的修复。

struct list *delete_node(struct list *l, int x) {
    struct list *prev, *retval=l;
    while (l) {
        if(l->value == x) {
            if(l==retval) {
                retval=l->next;
                free(l);
                l=retval;
            } else {
                prev->next=l->next;
                free(l);
                l=prev;
            }
        }
        prev = l;
        l = l->next;
    }

    return retval;
}

您不需要分配更多内存来丢弃不需要的节点。这样做会严重泄漏内存。

您需要跟踪列表的头部。这就是 retval 的用途。如果 x 未找到或在非头节点中找到，您将 return 相同的头。如果在头节点中找到 x，您将 return 下一个节点。

您还需要跟踪前一个节点，以便能够告诉前一个节点当前节点将被释放。这对于单个 link 列表是必需的。

Answer 2

删除的关键是保持对之前模式的跟踪。

通过以 "fake" 头节点开始，简化了 while 循环。

  struct list *delete_node(struct list *l, int x) {
    struct list start;  // Code only uses the next field
    start.next = l;
    struct list *p = &start;
    while (p->next) {
      struct list *q = p->next;
      if (q->value == x) {
        p->next = q->next;
        free(q);
        break;
        }
      p->next = q;
    }
    return start.next;
  }

C 删除链表中的节点

C delete node in a linked list

c

c++

linked-list