删除带头结点的单链表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)。