使用递归算法删除不带头结点单链表L中所有值为X的结点

设计一个递归算法，删除不带头结点的单链表L中所有值为X的结点。

根据题目中，删除单链表L中所有值为X的结点，也就把if(data == x)的值删掉。本题的重点是考察递归算法，同时要求单链表不带头结点。 那么，下面具体看看使用递归算法是如何实现的。

一、递归算法代码

void Del_X_recursion(Linklist &L,int X)
 {
	if(L == NULL) return; // 递归函数出口return；
	if(L->data !=X) // 若L所指结点的值不为X
	{
		Del_X_recursion(L->next,X);// 递归调用
		return; //递归出口return；
	}
	if(L->data ==X) 
	{
	LNode *p;
	p=L;  // p指向要删除的结点
	L=L->next;
	delete p;
	Del_X_recursion(L,X);// 递归调用
	}
 }

二、递归代码图文详解

如上图,假如有n个结点，从第一个结点开始遍历，若我们第一个结点为X，那么要完成删除链表中所有值为X的结点，相当于第一个结点已经知道了，后面的n-1结点也按照同样的方法操作就可以了。

如上图，假如第一个结点要留下，后面的n-1结点使用Del_X_recursion(L->next,X)递归函数执行完毕，在执行过程中肯定有留下来的，也有删掉的，但我们不必知道里面具体是如何实现的。只要后面n-1个结点执行完毕后，这个递归函数就可以结束了。

然后从最里层返回到上一层，一直return第一层，程序结束。出口函数结束。

最后是删除X结点的操作，如下图

(1)p=L;假如p指针指向的第一个结点为X，这是我们要删除的结点；

(2)L=L->next;接下来L指向下一个结点

(3)delete p;删除X结点

最后，再次调用Del_X_recursion(L,X);递归函数，从L开始，把其作为第一个结点递归的调用。一直将所有的X删除为止。