删除带头结点的单链表L中所有值为x的节点并释放其空间

问题描述：

在带头结点的单链表L中，删除所有值为x的结点，并释放其空间，假设值为x的结点不唯一，试编写算法以实现上述操作。

问题解答：

解法一：用p从头至尾扫描单链表，pre指向*p结点的前驱。若p所指结点的值为x，则删除，并让p移向下一个结点，否则让pre、p指针同步后移一个结点。

本题代码如下：

void Del_X_1(Linklist &L, ElemType x){
    //L为带头的单链表，本算法删除L中所有值为x的结点
    LNode *p=L->next, *pre=L, *q; //置 p 和 pre 的初始值
    while(p!=NULL){
        if(p->data==x){
            q=p;  //q指向该结点
            p=p->next;
            pre->next=p;  //删除*q 结点
            free(q);  //释放 *q结点的空间
        }else{  //否则，pre和p同步后移
           pre=p;
           p=p->next;
        }  //else
    }  //while
}

本算法是在无序单链表中删除满足某种条件的所有结点，这里的条件是结点的值为x。实际上，这个条件是可以任意指定的，只要修改if条件即可，比如，我们要求删除值介于 mink和maxk之间的所有结点，则只需将if语句修改为if(p->data>mink &&p->data<maxk)。

解法二：用尾插法建立单链表。用p指针扫描L的所有结点，当其值不为x时将其链接到L之后，否则将其释放。

本题代码如下：

void Del_X_2(Linklist &L, ElemType x){
    //L为带头的单链表，本算法删除L中所有值为x的结点
    LNode *p=3->next, *r=L, *q; //r指向尾结点，其切值为头结点
    while(p!=NULL){
        if (p->data!=x) {  //*p结点值不为x时将其链接到L尾部
            r->next=p;
            r=p;
            p=p->next;  //继续扫描
        }else{  //*p结点值为x时将其释放
            q=p;
            p=p->next;  //继续扫描
            free(q);  //释放空间
        }
    }//while
    r->next=NULL;  //插入结束后置尾结点指针为NULL
}

上述两个算法扫描一遍链表，时间复杂度为O(n)，空间复杂度为O(1)。