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

问题描述：

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

问题解答：

设f(L, x)的功能是删除以L为首结点指针的单链表中所有值等于x的结点，则显然有 f(L->next, x)的功能是删除以L->next为首结点指针的单链表中所有值等于x的结点。由此，可以推出递归模型如下：

终止条件：

• f(L, x) ≡ 不做任何事情;    若L为空表或只有一个结点
• f(L, x)≡删除*L 结点;f(L->next, x);       若 L->data==x

递归主体：

• f(L, x)≡f(L->next, x);    其他情况

本题代码如下：

void Del_X_3 (Linklist &L, ElemType x) {
    //递归实现在单链表L中删除值为x的结点
    LNode *p;  //p指向待删除结点
    if (L==NULL)  //递归出口
        return;
    if (L->data==x) {  //若L所指结点的值为x
        p=L;  //删除*L,并让L指向下一结点
        L=L->next;
        free(p);
        Del_X_3(L,x) ;  //递归调用
    }else  //若L所指结点的值不为x
        Del_X_3 (L->next, x) ;  //递归调用
}

算法需要借助一个递归工作栈，深度为O(n)，时间复杂度为O(n)。有读者认为直接free掉p结点会造成断链，实际上因为L为引用，是直接对原链表进行操作，因此不会断链。