Question

单链表不带表头结点，编写递归算法删除单链表中所有值为X的元素

Answer 1

#include <iostream>
using namespace std;

struct Link
{
int data;
Link *next;
};

/*
============================================
参数说明：[IN]head:当前的头结点的地址
[IN]prior:当前头结点的上一个节点
[IN]x:将值为x的节点删除
============================================
*/
void DeleteX(Link **head, Link *prior, int x)
{
if (*head != NULL)
{
if (prior == NULL && (*head)->data == x)
{
Link *p = *head;
*head = p->next;
delete p;
DeleteX(head, NULL, x);
}
else if (prior != NULL && (*head)->data == x)
{
prior->next = (*head)->next;
delete *head;
*head = prior->next;
DeleteX(head, prior, x);
}
else
{
prior = *head;
*head = prior->next;
DeleteX(head, prior, x);
}
}
}

void Add(Link **head, int data)
{
if (*head == NULL)
{
*head = new Link;
(*head)->data = data;
(*head)->next = NULL;
}
else
{
Add(&(*head)->next, data);
}
}

void Travel(Link *head)
{
while (head != NULL)
{
cout << head->data << ' ';
head = head->next;
}
cout << endl;
}

int main(void)
{
int a[10] = {7, 3, 4, 2, 6, 8, 2, 9, 0, 2}, i;
Link *head = NULL, *p = NULL;

for (i=0; i<10; ++i)
{
Add(&head, a[i]);
}
Travel(head);
p = head;
DeleteX(&p, NULL, 2);

Travel(head);

return 0;
}