博客

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

//定义一个单链表
typedef struct LNode {
	ElemType data;
	struct LNode* next;
}LNode, * LinkList;
//初始化单链表
bool InitList(LinkList& L) {
	L = NULL;	//空表，防止脏数据
	return true;
}
void Del_X(LinkList& L,ElemType x) {
	LNode* p;	
	if (L == NULL)
		return;	//递归出口
	if (L->data == x) {	//删除x
		p = L;	//p指向待删除结点
		L = L->next;
		free(p);
		Del_X(L, x);	//继续进行递归，因为前面已经让L指向了next,所以这里的第一个参数是L
	}
	else	//若L所指结点的值不为x
		Del_X(L->next, x);	//递归
}

算法深度为O(n)，时间复杂度为O(n)