## 问题描述 > 设计一个递归算法，删除不带头节点的单链表L中所有值为x的结点。 ## 算法思想 因为题目要求使用递归的方式删除指定结点，那么我们可以先列出递归的基本模型： > 指针p指向要删除的结点，指针q则为要删除结点的后继结点。 递归出口： ~~~ if(p==NULL){ return; } ~~~ 递归主体： ~~~ if(p->data==x){ p->data=q->data; p->next=q->next; free(q); DelNodeX(p,x); }else{ DelNodeX(p->next,x); } ~~~ 因为本题中，没有设置头节点，当删除的时候必须从第一个结点开始删除，因此我们参考[第1章第2节线性表的链式表示(1)](http://blog.csdn.net/u013595419/article/details/50481785)中的[2.5.2删除自身结点](http://blog.csdn.net/u013595419/article/details/50481785#t12)来实现该算法。应当注意到如果最后一个结点的数据域为x时，需要区别对待。此时，指针q为空，如果继续执行`p->data=q->data`时明显会出错，但也因为是最后一个结点，此时只需将指针p直接赋值为NULL便可。 算法描述如下： ## 算法描述 ~~~ void DelNodeX(LNode *p, ElemType x) { if(p==NULL){ return; } LNode* q=p->next; if(p->data==x){ if(q!=NULL){ p->data=q->data; p->next=q->next; }else{ p=NULL; } free(q); DelNodeX(p,x); }else{ DelNodeX(p->next,x); } } ~~~ 具体代码见附件 ## 附件 ~~~ #include<stdio.h> #include<stdlib.h> typedef int ElemType; typedef struct LNode{ ElemType data; struct LNode *next; }LNode,*LinkList; LinkList CreatList(); void DelNodeX(LNode*,ElemType); void Print(LNode*); int main(int argc,char* argv[]) { ElemType e=3; LNode *p; p=CreatList(); Print(p); DelNodeX(p,e); Print(p); return 0; } //尾插法建立单链表 LinkList CreatList() { LNode *p; LNode *s; ElemType x; scanf("%d",&x); p=(LNode*)malloc(sizeof(LNode)); p->data=x; LNode *r=p; while(1){ scanf("%d",&x); if(x==999){ break; } s=(LNode*)malloc(sizeof(LNode)); s->data=x; r->next=s; r=s; } r->next=NULL; return p; } //删除指定节点 void DelNodeX(LNode *p, ElemType x) { if(p==NULL){ return; } LNode* q=p->next; if(p->data==x){ if(q!=NULL){ p->data=q->data; p->next=q->next; }else{ p=NULL; } free(q); DelNodeX(p,x); }else{ DelNodeX(p->next,x); } } //打印所有节点 void Print(LNode *p) { while(p){ printf("%4d",p->data); p=p->next; } printf("\n"); } ~~~ 注：此种解法存在一个Bug，当最后一个或最后多个连续结点均为数据域为x的结点时，会留下一个数据域为x的结点，目前个人暂没想到解决办法，改天再想。