时间戳

首页 > 解决方案 > 使用递归删除链表中所有出现的数字

c - 使用递归删除链表中所有出现的数字

问题描述

我想编写一个程序，使用递归从一个简单的链表中删除所有出现的数字，所以我尝试了但我遇到了问题：我编写的程序会擦除列表中的所有出现但它不会删除那个存在于开头（出现在第一个节点处），这是C中的代码：

typedef struct list {
    int data;
    struct list *next;
} list;

list *delete(int x, list *head) {
    if (head->next == NULL)
        return head;
    list *newnode = delete(x, head->next);
    if (newnode->data == x) {
        head->next = head->next->next;
        free(newnode);
    }
    return head;
}

我希望有人可以帮助我改进我的算法，在此先感谢。

标签： calgorithmrecursionlinked-list

解决方案

这段代码：

    if(head->next == NULL)
        return head;

显式地使函数返回任何 1 元素列表不变。这会产生您描述的问题，因此在那里没有任何意义。

我想应该可以递归地制定列表元素的删除，尽管它肯定不是一种常见/典型/好方法。

这可能有效，未经测试：

list * delete(list *head, int value)
{
  if (head == NULL)
    return NULL;
  if (head->data == value)
  {
      list * tail = head->next;
      free(head);
      return delete(tail, value);
  }
  // List was not empty and did not start with the value,
  // so set the tail of the list to the tail without the value.
  head->next = delete(head->next, value);
  return head;
}

推荐阅读